Remove Nodes From Linked List

This approach uses a straightforward, brute-force method. It iterates through each node of the linked list, and for each node, it performs a second scan through all the subsequent nodes to check if there exists any node with a strictly greater value. If a greater value is found, the current node is removed from the 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.

/**
 * 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 {
    public ListNode removeNodes(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode current = head;
        ListNode prev = dummy;

        while (current != null) {
            boolean foundGreater = false;
            ListNode runner = current.next;
            while (runner != null) {
                if (runner.val > current.val) {
                    foundGreater = true;
                    break;
                }
                runner = runner.next;
            }

            if (foundGreater) {
                // Remove current node by linking prev to current's next
                prev.next = current.next;
            } else {
                // Keep current node, so update prev
                prev = current;
            }
            // Move to the next node in the original list
            current = current.next;
        }
        return dummy.next;
    }
}