Remove Zero Sum Consecutive Nodes from Linked List

Quick Links

Problem Description

The “Remove Zero Sum Consecutive Nodes from Linked List” problem involves removing nodes from a linked list where the sum of consecutive nodes equals zero.
Imagine cleaning out your fridge after a long vacation—if something smells bad (or sums to zero), it’s got to go!

For example, if you have a linked list like this: 1 -> 2 -> -3 -> 3 -> 1, the 2 and -3 cancel each other out, leaving you with 1 -> 3 -> 1.

Code Solution


class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        dummy = ListNode(0, head)
        prefix = 0
        prefixToNode = {0: dummy}

        while head:
            prefix += head.val
            prefixToNode[prefix] = head
            head = head.next

        prefix = 0
        head = dummy

        while head:
            prefix += head.val
            head.next = prefixToNode[prefix].next
            head = head.next

        return dummy.next

Approach Explanation

The approach uses a prefix sum to track the cumulative sum of the linked list. If the same prefix sum is encountered again, it indicates that the nodes in between sum to zero, allowing us to remove them.

Initialization: Create a dummy node to handle edge cases and a dictionary to map prefix sums to their corresponding nodes.
First Pass: Traverse the list, updating the prefix sum and storing the last occurrence of each sum.
Second Pass: Traverse again, using the stored sums to skip over nodes that sum to zero.

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list.

Space Complexity: O(n) due to the storage of prefix sums in a dictionary.

Real-World Example

Think of this problem like a group of friends trying to decide where to eat. If two friends suggest a restaurant that everyone else hates (a zero-sum situation), they might cancel each other out and lead the group to a better choice.
In the end, you’re left with a happy group and a delicious meal—just like our linked list after removing those pesky zero-sum nodes!