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 Zero Sum Consecutive Nodes from Linked List

Number: 1267

Difficulty: Medium

Paid? No

Companies: josh technology, Microsoft, Amazon, Apple, Uber

Problem Description

Given the head of a linked list, repeatedly remove consecutive sequences of nodes that sum to 0 until no such sequences remain, and return the head of the final linked list.

Key Insights

  • Use a dummy node to handle edge cases such as the removal of nodes at the head.
  • Compute a running (prefix) sum while traversing the list.
  • Use a hash table (or hashmap) to map each prefix sum to the most recent node where that sum occurred.
  • If the same prefix sum is encountered again, the nodes in between sum to 0 and can be removed by adjusting pointers.
  • Perform two passes: the first to record prefix sums and their corresponding nodes, and the second to remove zero-sum sequences.

Space and Time Complexity

Time Complexity: O(n) - Two passes over the list. Space Complexity: O(n) - Hash table storing at most n prefix sums.

Solution

The solution uses a two-pass algorithm with a hash table. In the first pass, compute the prefix sum for each node and store the mapping from prefix sum to the node (overwriting with the latest occurrence). This ensures that for any repeated prefix sum, the nodes in between sum to 0. In the second pass, traverse the list again and use the hash table to skip the zero-sum subsequences by redirecting the next pointer of a node to the next pointer of the stored node for that prefix sum. Key data structures are the hash table and a dummy node to simplify pointer adjustments.

Code Solutions

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

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        # Create a dummy node to simplify cases where removal starts at the head.
        dummy = ListNode(0)
        dummy.next = head

        # Dictionary to store prefix sum to node mapping.
        sum_to_node = {}
        prefix_sum = 0
        current = dummy
        
        # First pass: record the last occurrence of each prefix sum.
        while current:
            prefix_sum += current.val
            sum_to_node[prefix_sum] = current
            current = current.next
        
        # Second pass: remove nodes that are part of zero-sum sequences.
        prefix_sum = 0
        current = dummy
        while current:
            prefix_sum += current.val
            # Link current node's next pointer to skip the zero-sum subsequence.
            current.next = sum_to_node[prefix_sum].next
            current = current.next
        
        return dummy.next
← Back to All Questions