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

Difficulty: Medium

Problem Description

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences. After doing so, return the head of the final linked list. You may return any such answer.

Key Insights

  • A consecutive sequence of nodes can be identified by keeping track of cumulative sums.
  • Using a hash map (or dictionary), we can store the cumulative sum and its corresponding node, which helps in detecting zero-sum sequences.
  • If a cumulative sum is found again, it indicates that the nodes between the first occurrence and the current occurrence sum to zero and should be removed.
  • The process continues until no more zero-sum sequences can be found.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list. Each node is processed at most twice. Space Complexity: O(n), for storing cumulative sums in a hash map.

Solution

We can approach this problem by using a hash map to track the cumulative sum of the linked list nodes. As we traverse the linked list, we compute the cumulative sum and check if it has been seen before. If it has, we remove the nodes that contribute to the zero-sum. Finally, we return the modified linked list.

Code Solutions

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

def removeZeroSumSublists(head: ListNode) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    cumulative_sum = 0
    sum_map = {0: dummy}  # To handle the case where the head itself is part of a zero-sum sequence

    # First pass to get cumulative sums
    current = head
    while current:
        cumulative_sum += current.val
        sum_map[cumulative_sum] = current
        current = current.next

    # Second pass to remove zero-sum sequences
    cumulative_sum = 0
    current = dummy
    while current:
        cumulative_sum += current.val
        current.next = sum_map[cumulative_sum].next  # Skip the nodes that sum to zero
        current = current.next

    return dummy.next
← Back to All Questions