给你一个链表的头节点?
head
?。移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点?
head
?。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
}
};
可见题目要求我们把原链表修改为一个非升序链表,那么我们只需要遍历一遍链表,维护一个单调栈存储节点,保证从栈底到栈顶单调递减,遍历完之后将栈中节点串联起来,栈底节点就是表头
时间复杂度:O(n) 空间复杂度:O(1)
?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
if(!head || !(head -> next))
return head;
stack<ListNode*> s;
s.push(head);
head = head -> next;
while(head)
{
while(s.size() && head -> val > s.top() -> val)
s.pop();
s.push(head);
head = head -> next;
}
while(s.size())
{
s.top() -> next = head;
head = s.top();
s.pop();
}
return head;
}
};