2487. Remove Nodes From Linked List
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
Linked List、Stack、Recursion、Monotonic Stack - \(\color{blue}\textsf{Weekly Contest 321}\)
一、題目
You are given the head of a linked list.
Remove every node which has a node with strictly greater value anywhere to the right side of it.
Return the head of the modified linked list.
Example 1:
- Input: head = [5,2,13,3,8]
- Output: [13,8]
- Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.
Example 2:
- Input: head = [1,1,1,1]
- Output: [1,1,1,1]
- Explanation: Every node has value 1, so no nodes are removed.
Constraints:
- The number of the nodes in the given list is in the range
[1, 10^5]. 1 <= Node.val <= 10^5
二、分析
- 這一題可以用
Monotonic Stack，將鏈表遍歷一次，遇到更大的數，就被堆上的值拿掉。 - 不過因為題目最後要回傳一個
Linked List，所以我會使用Deque來實作，遍歷完一次之後再把堆剩下的值，依序連接。
三、解題
1. Monotonic Stack
- Time complexity: \(O(n)\)
- Space complexity: \(O(n)\)
ListNode* removeNodes(ListNode* head) {
deque<ListNode*> dq;
dq.push_back(new ListNode(INT_MAX, head)); // 省去處理 deque 為空的狀況
ListNode* curr = head;
while (curr) {
while (curr->val > dq.back()->val) {
dq.pop_back();
}
dq.push_back(curr);
curr = curr->next;
}
ListNode* dummy = new ListNode(dq.front()->val);
curr = dummy;
dq.pop_front();
while (!dq.empty() && curr) {
curr->next = dq.front();
dq.pop_front();
curr = curr->next;
}
return dummy->next;
}