Problem

Given the head of a singly linked list, delete all nodes that have a greater value node on their right side. Return the modified list after deletion.

OR

Given a single linked list. Delete all the elements that has lager value element on right of it.

Examples

Example 1:

1
2

Input: head = 12 -> 15 -> 10 -> 11 -> 5 -> 6 -> 2 -> 3 -> null
Output: 15 -> 11 -> 6 -> 3 -> null

Example 2:

1
2

Input: head = 10 -> 20 -> 30 -> 40 -> 50 -> null
Output: 50 -> null

Example 3:

1
2

Input: head = 50 -> 40 -> 30 -> 20 -> 10 -> null
Output: 50 -> 40 -> 30 -> 20 -> 10 -> null

Solution

Method 1 - Reversing the list

  1. Reverse the Linked List:
    • Reverse the linked list to simplify the problem. This way, we can easily remove nodes that have a greater node on their right by comparing nodes during traversal.
  2. Traverse and Track the Maximum Node:
    • Traverse the reversed list and keep track of the maximum value node encountered so far. Delete nodes that have a lower value compared to the maximum node.
  3. Reverse the List Again:
    • Finally, reverse the list again to restore the original order, but with the desired nodes removed.

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

public class Solution {
    public ListNode deleteNodesWithGreaterRight(ListNode head) {
        if (head == null)
            return null;

        // Step 1: Reverse the linked list
        ListNode reversedHead = reverseList(head);

        // Step 2: Traverse and delete nodes with greater nodes on right
        ListNode current = reversedHead;
        ListNode maxNode = reversedHead;
        ListNode prev = reversedHead;

        while (current != null && current.next != null) {
            if (current.next.val < maxNode.val) {
                // Delete the node
                current.next = current.next.next;
            } else {
                current = current.next;
                maxNode = current;
            }
        }

        // Step 3: Reverse the list again
        return reverseList(reversedHead);
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null, current = head;
        while (current != null) {
            ListNode nextNode = current.next;
            current.next = prev;
            prev = current;
            current = nextNode;
        }
        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 deleteNodesWithGreaterRight(self, head: ListNode) -> ListNode:
        if not head:
            return None

        # Step 1: Reverse the linked list
        reversed_head = self.reverseList(head)

        # Step 2: Traverse and delete nodes with greater nodes on the right
        max_node = reversed_head
        current = reversed_head
        prev = reversed_head

        while current and current.next:
            if current.next.val < max_node.val:
                # Delete the node
                current.next = current.next.next
            else:
                current = current.next
                max_node = current

        # Step 3: Reverse the list again
        return self.reverseList(reversed_head)

    def reverseList(self, head):
        prev, current = None, head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        return prev