Remove every node which has a node with a 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, 105].
1 <= Node.val <= 105
Solutions
Solution 1: Monotonic Stack Simulation
We can first store the node values of the linked list into an array $nums$. Then, we traverse the array $nums$, maintaining a stack $stk$ that is monotonically decreasing from the bottom to the top. If the current element is larger than the top element of the stack, we pop the top element of the stack until the current element is less than or equal to the top element, and then we push the current element into the stack.
Finally, we construct the resulting linked list from the bottom to the top of the stack, which is the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the linked list.
We can also directly traverse the linked list without using the array $nums$, maintaining a stack $stk$ that is monotonically decreasing from the bottom to the top. If the current element is larger than the top element of the stack, we pop the top element of the stack until the current element is less than or equal to the top element. Then, if the stack is not empty, we set the $next$ pointer of the top element of the stack to the current element. Otherwise, we set the $next$ pointer of the dummy head node of the answer linked list to the current element. Finally, we push the current element into the stack and continue to traverse the linked list.
After the traversal, we return the $next$ pointer of the dummy head node as the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the linked list.
1 2 3 4 5 6 7 8 910111213141516171819202122
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defremoveNodes(self,head:Optional[ListNode])->Optional[ListNode]:nums=[]whilehead:nums.append(head.val)head=head.nextstk=[]forvinnums:whilestkandstk[-1]<v:stk.pop()stk.append(v)dummy=ListNode()head=dummyforvinstk:head.next=ListNode(v)head=head.nextreturndummy.next
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcremoveNodes(head*ListNode)*ListNode{nums:=[]int{}forhead!=nil{nums=append(nums,head.Val)head=head.Next}stk:=[]int{}for_,v:=rangenums{forlen(stk)>0&&stk[len(stk)-1]<v{stk=stk[:len(stk)-1]}stk=append(stk,v)}dummy:=&ListNode{}head=dummyfor_,v:=rangestk{head.Next=&ListNode{Val:v}head=head.Next}returndummy.Next}
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcremoveNodes(head*ListNode)*ListNode{dummy:=&ListNode{1<<30,head}stk:=[]*ListNode{dummy}forcur:=head;cur!=nil;cur=cur.Next{forstk[len(stk)-1].Val<cur.Val{stk=stk[:len(stk)-1]}stk[len(stk)-1].Next=curstk=append(stk,cur)}returndummy.Next}