题目:给你一个链表的头节点 head 。
移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点 head 。
示例 1:
输入:head = [5,2,13,3,8]
输出:[13,8]
解释:需要移除的节点是 5 ,2 和 3 。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。
示例 2:
输入:head = [1,1,1,1]
输出:[1,1,1,1]
解释:每个节点的值都是 1 ,所以没有需要移除的节点。
法一;模拟,将链表存入数组
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
vector<int> nums,ans;
ListNode* p = head;
while(p) {
nums.push_back(p -> val);
p = p -> next;
}
int maxval = -1;
for(int i = nums.size()-1; i >= 0; -- i) {
if(nums[i] >= maxval) {
ans.push_back(nums[i]);
maxval = nums[i];
}
}
if(ans.size() == 0) return NULL;
ListNode*dummy = new ListNode(0);
dummy->next = NULL;
for(int j = 0; j < ans.size(); ++j) {
ListNode*q = new ListNode(ans[j]);
q -> next = dummy -> next;
dummy -> next = q;
}
return dummy -> next;
}
};
//暴力解法:将链表存入数组,倒着遍历并更新当前最大值,如果遍历元素值小于当前最大值,不加入答案数组;最后按头插法将答案数组构造成链表;
法二:先运用反转链表模板将链表反转,然后依次遍历删除比当前元素小的结点,最后再返回反转的链表,即可完成;
class Solution {
public:
ListNode* reverseList(ListNode*head) {
ListNode*pre = NULL, *cur = head;
while(cur) {
ListNode* nextnode = cur -> next;
cur -> next = pre;
pre = cur;
cur = nextnode;
}
return pre;
}
ListNode* removeNodes(ListNode* head) {
ListNode*p = reverseList(head),*q = p;
while(p->next) {
if(p -> next -> val < p -> val) {
p -> next = p -> next -> next;
}else{
p= p -> next;
}
}
return reverseList(q);
}
};