Remove Nodes From Linked List

MEDIUM

Description

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:

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:

Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: 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, 10⁵].
1 <= Node.val <= 10⁵

Approaches

Checkout 4 different approaches to solve Remove Nodes From Linked List. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Nested Loops

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.

Algorithm

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;
    }
}

Complexity Analysis

Time Complexity: O(N^2) - For each node in the list (N nodes), we may traverse the rest of the list (up to N-1 nodes). This results in a nested loop structure, giving a quadratic time complexity.Space Complexity: O(1) - We only use a constant number of extra pointers (`dummy`, `prev`, `current`, `runner`) regardless of the list size.

Pros and Cons

Pros:

The logic is simple and easy to understand.
It operates in-place and uses O(1) extra space.

Cons:

The time complexity of O(N^2) is highly inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints (N up to 10^5).

Code Solutions

Checking out 3 solutions in different languages for Remove Nodes From Linked List. Click on different languages to view the code.

/** * 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 ) { List < Integer > nums = new ArrayList <>(); while ( head != null ) { nums . add ( head . val ); head = head . next ; } Deque < Integer > stk = new ArrayDeque <>(); for ( int v : nums ) { while (! stk . isEmpty () && stk . peekLast () < v ) { stk . pollLast (); } stk . offerLast ( v ); } ListNode dummy = new ListNode (); head = dummy ; while (! stk . isEmpty ()) { head . next = new ListNode ( stk . pollFirst ()); head = head . next ; } return dummy . next ; } }

Video Solution

Watch the video walkthrough for Remove Nodes From Linked List

Patterns:

Recursion

Data Structures:

Linked ListStackMonotonic Stack