Table of Contents
Description: Remove Nodes From Linked List
You are given the head
of a linked list.
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
1 2 3 4 5 6 |
<strong>Input:</strong> head = [5,2,13,3,8] <strong>Output:</strong> [13,8] <strong>Explanation:</strong> 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
1 2 3 |
<strong>Input:</strong> head = [1,1,1,1] <strong>Output:</strong> [1,1,1,1] <strong>Explanation:</strong> 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
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { //use stack public ListNode removeNodes(ListNode head) { ArrayDeque<ListNode> stack = new ArrayDeque<>(); ListNode p = head; while(p!=null){ //if the stack is not empty or the current node val is greater than the previous node, pop an element from the stack while(!stack.isEmpty() && stack.peek().val < p.val){ stack.pop(); } stack.push(p); p = p.next; } p = stack.pop(); //update the next pointer while(!stack.isEmpty()){ ListNode n = stack.pop(); n.next = p; p = n; } return p; } } |
Time Complexity
O(n), where n is the number of nodes in a linkedlist
Space Complexity
O(n), where n is the number of nodes in a linkedlist