We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Nodes From Linked List

Number: 2573

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Bloomberg, Uber, Adobe

Problem Description

Given the head of a linked list, remove every node that has a node with a greater value somewhere to its right. Return the head of the modified linked list.

Key Insights

  • A node should be kept only if no node to its right has a greater value.
  • Reversing the list simplifies the problem by converting the "right" side into a "left" side.
  • While traversing the reversed list, maintain the maximum value encountered.
  • Remove any node that is smaller than this maximum, since it means there was a larger node originally to its right.
  • Finally, reverse the list back to the original order with only the required nodes remaining.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves three main steps:

  1. Reverse the linked list so that we process nodes from the end towards the beginning.
  2. Traverse the reversed list and maintain a variable (max_val) that stores the largest value seen so far. Skip any node that has a value less than max_val.
  3. Reverse the list again to restore the original order, now excluding the nodes that should be removed.

Data structures used:

  • The linked list itself is modified in place.
  • No additional data structure is needed for tracking aside from a simple variable for the maximum value.

This approach efficiently solves the problem in linear time while using constant extra space.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNodes(head):
    # Helper function to reverse a linked list.
    def reverse_list(node):
        prev = None
        curr = node
        while curr:
            nxt = curr.next           # Save next node
            curr.next = prev          # Reverse pointer
            prev = curr               # Move prev to current
            curr = nxt                # Move to next node
        return prev

    # Reverse the list to process from the tail.
    rev_head = reverse_list(head)
    
    current = rev_head
    max_val = rev_head.val          # Maximum value seen so far in reversed list
    
    # Traverse the reversed list and remove nodes that are less than max_val.
    while current and current.next:
        if current.next.val < max_val:
            current.next = current.next.next  # Skip the node with lower value
        else:
            current = current.next
            max_val = current.val   # Update max_val with the new larger value
    
    # Reverse the list again to restore original order.
    return reverse_list(rev_head)
← Back to All Questions