Scale Engineer

Remove Nodes From Linked List

Med
#2269Time: 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: O(1) - We only use a constant number of extra pointers (`dummy`, `prev`, `current`, `runner`) regardless of the list size.
Patterns
Recursion
Data structures
Linked ListStackMonotonic Stack

Prompt

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, 105].
  • 1 <= Node.val <= 105

Approaches

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1) - We only use a constant number of extra pointers (`dummy`, `prev`, `current`, `runner`) regardless of the list size.

Trade-offs

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).

Solutions

/** * 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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem