Problem

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.

Examples

Example 1:

graph LR;
   A[5] --> B[2] --> C[13] --> D[3] --> E[8];
   style C fill:#32CD32;
   style E fill:#32CD32;
  
1
2
3
4
5
6

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:

1
2
3

Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.

Solution

Method 1 - Reverse the list

Here is the approach:

  1. Reverse Traversal: To solve this problem, we can leverage the reverse traversal of the linked list. By traversing the list from the end to the beginning, we can keep track of the maximum value encountered so far and remove nodes that are smaller than this maximum.
  2. Reversing the List: Firstly, reverse the linked list. This allows us to easily track the maximum value encountered in a single traversal.
  3. Filtering Nodes: Traverse the reversed linked list, keeping the maximum value encountered and removing nodes smaller than this maximum value.
  4. Reverse the List Back: Finally, reverse the list again to restore the original order with the nodes removed as required.

Code

 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
38
39

class Solution {
    public ListNode removeNodes(ListNode head) {
        if (head == null) return null;
        
        // Step 1: Reverse the linked list
        head = reverse(head);
        
        // Step 2: Filter nodes
        ListNode newHead = head;
        ListNode maxNode = head;
        ListNode curr = head.next;
        maxNode.next = null;  // new head of modified list
        
        while (curr != null) {
            ListNode next = curr.next;
            if (curr.val >= maxNode.val) {
                curr.next = newHead;
                newHead = curr;
                maxNode = curr;
            }
            curr = next;
        }
        
        // Step 3: Reverse the modified list back to original order
        return reverse(newHead);
    }
    
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

}
 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

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        
        # Step 1: Reverse the linked list
        head = self.reverse(head)
        
        # Step 2: Filter nodes
        new_head = head
        max_node = head
        curr = head.next
        max_node.next = None  # new head of modified list
        
        while curr:
            next_node = curr.next
            if curr.val >= max_node.val:
                curr.next = new_head
                new_head = curr
                max_node = curr
            curr = next_node
        
        # Step 3: Reverse the modified list back to original order
        return self.reverse(new_head)
    def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        while head:
            next_node = head.next
            head.next = prev
            prev = head
            head = next_node
        return prev

Complexity

  • ⏰ Time complexity:  O(n), where n is the number of nodes in the linked list. We traverse the list three times (reversing twice and filtering once).
  • 🧺 Space complexity: O(1), since we only use a few extra pointers and variables without extra space proportional to input size.