Remove Zero Sum Consecutive Nodes from Linked List

Quick Links

Code Solution


class Solution {
  public ListNode removeZeroSumSublists(ListNode head) {
    ListNode dummy = new ListNode(0, head);
    int prefix = 0;
    Map prefixToNode = new HashMap<>();
    prefixToNode.put(0, dummy);

    for (; head != null; head = head.next) {
      prefix += head.val;
      prefixToNode.put(prefix, head);
    }

    prefix = 0;

    for (head = dummy; head != null; head = head.next) {
      prefix += head.val;
      head.next = prefixToNode.get(prefix).next;
    }

    return dummy.next;
  }
}

Problem Description

So, you’ve got a linked list, and it’s looking a bit bloated. The problem is, some of these nodes are adding up to zero, and we need to get rid of them. The task is to remove consecutive nodes from the linked list that sum up to zero.

Imagine you’re at a buffet, and you keep piling food on your plate, but every time you add a certain dish, it cancels out the calories from another dish. You end up with a plate that has zero calories. Now, wouldn’t it be great if you could just magically make those zero-calorie dishes disappear? That’s exactly what we’re doing here!

Approach Explanation

The provided solution uses a clever approach involving prefix sums and a hashmap. Here’s a brief breakdown:

Dummy Node: We start with a dummy node to handle edge cases easily.
Prefix Sum Calculation: As we traverse the list, we calculate the prefix sum and store the last occurrence of each sum in a hashmap.
Removing Zero-Sum Sublists: In a second pass, we use the hashmap to skip over nodes that lead to a zero-sum.

This way, we efficiently remove all consecutive nodes that sum to zero without needing to traverse the list multiple times.

Time and Space Complexity

Complexity	Details
Time Complexity	O(n), where n is the number of nodes in the linked list. We traverse the list a couple of times, but each traversal is linear.
Space Complexity	O(n) as well, due to the hashmap storing the prefix sums.

Real-World Example

Let’s say you’re at a party, and you keep meeting people who owe you money. Every time you meet someone who owes you exactly what you owe to someone else, you just wave them off, and poof! Your debts cancel out. This is similar to how we remove zero-sum nodes from the linked list. We keep track of our “debts” (the prefix sums) and eliminate those that balance out to zero.