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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Nodes From Linked List

Difficulty: Medium

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

Key Insights

  • A node should be removed if there exists a node to its right with a greater value.
  • The problem can be approached by traversing the linked list from right to left, keeping track of the maximum value encountered.
  • A stack can be utilized to maintain the nodes that should remain in the list, as we can easily check against the maximum value.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list, since we need to traverse the entire list once. Space Complexity: O(n), for storing the nodes in the stack if all nodes are kept.

Solution

The solution involves using a stack to store the nodes that need to be retained. We traverse the linked list from the end to the beginning, comparing each node's value with the maximum value seen so far. If the current node's value is greater than or equal to this maximum value, it is pushed onto the stack. After the traversal, the nodes are popped from the stack to form the modified linked list.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNodes(head: ListNode) -> ListNode:
    stack = []
    current = head
    max_value = float('-inf')
    
    # Traverse the linked list from the end to the beginning
    while current:
        if current.val >= max_value:
            stack.append(current)  # Keep the node
            max_value = current.val  # Update max_value
        current = current.next
    
    # Reconstruct the linked list from the stack
    dummy = ListNode(0)
    current = dummy
    while stack:
        current.next = stack.pop()  # Pop from stack to get the correct order
        current = current.next
    
    current.next = None  # Terminate the list
    return dummy.next
← Back to All Questions