Remove Nodes From Linked List

• Create a dummy node that points to the head to simplify edge cases like removing the original head.
• Use two pointers, prev and current. prev will point to the last node that was kept, and current will iterate through the list.
• For each current node, start another pointer runner from current.next.
• Iterate with runner through the rest of the list. If any runner.val > current.val, it means current must be removed.
• If current needs to be removed, update prev.next to point to current.next, effectively skipping current.
• If current does not need to be removed (i.e., the inner loop finishes without finding a greater value), then current is a valid node in the final list, so we update prev to current.
• Advance current to the next node in the list and repeat the process.
• Finally, return dummy.next which points to the head of the modified list.

The core idea is to check the removal condition for each node one by one. We can use a dummy head to make the removal of the first node easier. We iterate through the list with a current pointer. For each current node, we use a runner pointer to scan the rest of the list to its right. If the runner finds any node with a value greater than current.val, we know current must be removed. To remove it, we need a pointer to the node before current, let's call it prev. We update prev.next to current.next. If the entire scan to the right of current completes without finding a greater node, we keep current and simply advance prev to current. This nested loop structure leads to a quadratic time complexity.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode removeNodes(ListNode head) {13        ListNode dummy = new ListNode(0, head);14        ListNode current = head;15        ListNode prev = dummy;16 17        while (current != null) {18            boolean foundGreater = false;19            ListNode runner = current.next;20            while (runner != null) {21                if (runner.val > current.val) {22                    foundGreater = true;23                    break;24                }25                runner = runner.next;26            }27 28            if (foundGreater) {29                // Remove current node by linking prev to current's next30                prev.next = current.next;31            } else {32                // Keep current node, so update prev33                prev = current;34            }35            // Move to the next node in the original list36            current = current.next;37        }38        return dummy.next;39    }40}

• Define a recursive function that takes the head of a list (or sublist) as input.
• Base Case: If the head is null or head.next is null, it means we are at the end of the list. No node can be to its right, so we return the head itself.
• Recursive Step: Make a recursive call for the rest of the list: removeNodes(head.next). This call will return the head of the processed sublist that follows the current head.
• Let the returned node be nextNode. This nextNode is the first node in the valid, modified remainder of the list.
• Compare the current head.val with nextNode.val. Since nextNode is the head of the modified sublist, all nodes that were smaller than it have already been removed. Thus, nextNode holds the largest value at the start of the sublist.
• If head.val < nextNode.val, the current head must be removed. We do this by returning nextNode from the current function call, effectively bypassing head.
• If head.val >= nextNode.val, the current head should be kept. We link it to the modified rest of the list by setting head.next = nextNode and return head.
• The initial call to removeNodes(head) will return the head of the final, fully modified list.

The function removeNodes(head) will solve the problem for the list starting at head. The key insight is to first solve the problem for the rest of the list, head.next. The recursive call removeNodes(head.next) returns a nextNode which is the head of the already-processed remainder of the list. Now, we only need to decide the fate of the current head. The head should be removed if its value is less than the value of nextNode (since nextNode is a node to its right). If head is kept, its next pointer should point to nextNode. This post-order processing ensures that when we decide about head, the list to its right has already been correctly filtered.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode removeNodes(ListNode head) {13        if (head == null || head.next == null) {14            return head;15        }16        ListNode nextNode = removeNodes(head.next);17        if (head.val < nextNode.val) {18            // The current node should be removed.19            // Return the head of the modified rest of the list.20            return nextNode;21        } else {22            // The current node should be kept.23            // Link it to the modified rest of the list.24            head.next = nextNode;25            return head;26        }27    }28}

• Initialize an empty stack, which will store ListNode objects.
• Iterate through the linked list from head to tail with a current pointer.
• For each current node:
  • While the stack is not empty and the value of the node at the top of the stack (stack.peek().val) is less than current.val, pop from the stack. This step removes all nodes that are followed by a greater node (current).
  • After the loop, push the current node onto the stack.
• After iterating through the entire list, the stack contains the nodes of the final list, but in reverse order.
• To construct the final list, create a new head (initially null). Repeatedly pop from the stack, and for each popped node, set its next pointer to the current head and then update head to be the popped node. This reverses the order and links the nodes correctly.
• Return the new head.

By using a stack, we can efficiently find the next greater element for a sequence of nodes. As we traverse the list, we maintain a stack of nodes that are potential candidates for the final list. When we encounter a current node, we compare it with the node at the top of the stack. If current.val is greater, it means the node on the stack must be removed. We continue popping until the stack is empty or the node at the top is greater than or equal to current. Then, we push current onto the stack. This ensures the stack always holds a sequence of nodes with decreasing values. After one pass, the nodes remaining in the stack are precisely the ones that should be in the final list, but in reverse order. A second pass over the stack elements allows us to rebuild the linked list in the correct order.

1import java.util.ArrayDeque;2import java.util.Deque;3 4/**5 * Definition for singly-linked list.6 * public class ListNode {7 *     int val;8 *     ListNode next;9 *     ListNode() {}10 *     ListNode(int val) { this.val = val; }11 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }12 * }13 */14class Solution {15    public ListNode removeNodes(ListNode head) {16        Deque<ListNode> stack = new ArrayDeque<>();17        ListNode current = head;18 19        while (current != null) {20            while (!stack.isEmpty() && stack.peek().val < current.val) {21                stack.pop();22            }23            stack.push(current);24            current = current.next;25        }26 27        ListNode newHead = null;28        while (!stack.isEmpty()) {29            ListNode node = stack.pop();30            node.next = newHead;31            newHead = node;32        }33 34        return newHead;35    }36}

• Step 1: Reverse the list. Implement a helper function to reverse the linked list. Call it on the original head. The original tail is now the new head.
• Step 2: Filter the nodes. Traverse the reversed list. Keep track of the maximum value seen so far (max_so_far), initialized to the value of the new head.
  • Use a prev pointer to track the last node that was kept and a current pointer to iterate.
  • If current.val is less than max_so_far, it means this node has a greater value to its left (which was its right in the original list). Remove it by setting prev.next = current.next.
  • If current.val is greater than or equal to max_so_far, keep this node. Update max_so_far = current.val and advance prev to current.
• Step 3: Reverse the list again. The filtered list is now correct but in reverse order. Call the reverse function again on the head of this modified list to restore the original relative order of the kept nodes.

First, we reverse the entire linked list. For an input of [5,2,13,3,8], this gives us [8,3,13,2,5]. Now, we can iterate through this reversed list and keep only the nodes that form a non-increasing sequence when read from left to right. We can do this by keeping track of the maximum value seen so far. We start with max_so_far = 8. Then we see 3, which is less than 8, so we remove it. Then we see 13, which is greater than 8, so we keep it and update max_so_far = 13. Then we see 2 and 5, both less than 13, so they are removed. The resulting list is [8, 13]. Finally, we reverse this list again to get [13, 8], which is the correct output. This entire process takes two full passes over the list data (two reversals and one filtering pass), resulting in linear time complexity, but crucially, it uses only a constant amount of extra space.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode removeNodes(ListNode head) {13        // Step 1: Reverse the linked list14        ListNode reversedHead = reverseList(head);15 16        ListNode current = reversedHead;17        int maxVal = Integer.MIN_VALUE;18        ListNode prev = null;19 20        // Step 2: Traverse the reversed list and remove nodes21        while (current != null) {22            if (current.val >= maxVal) {23                // Keep this node24                maxVal = current.val;25                prev = current;26            } else {27                // Remove this node by skipping it28                prev.next = current.next;29            }30            current = current.next;31        }32 33        // Step 3: Reverse the list again to get the final result34        return reverseList(reversedHead);35    }36 37    private ListNode reverseList(ListNode node) {38        ListNode prev = null;39        ListNode current = node;40        while (current != null) {41            ListNode nextTemp = current.next;42            current.next = prev;43            prev = current;44            current = nextTemp;45        }46        return prev;47    }48}