Abstract / Summary

Remove consecutive nodes in a linked list whose values sum to zero.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 53% (300k+ submissions).

Typical patterns to solve this problem:

• Hash Table
• Linked List

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that removes all consecutive sequences of nodes whose values sum to zero from a singly-linked list. It accomplishes this in two traversals: the first records the latest position where each cumulative sum occurs, and the second rewires the list based on those recorded positions. The approach guarantees that any zero-sum segment, regardless of its length or location, is eliminated from the final list.

First Traversal - Recording Prefix Sums

During the initial pass the algorithm walks through the original list while maintaining a running total of node values. For each cumulative sum it stores a reference to the node that follows the current one. This mapping enables the later step to jump over any segment whose sum returns to a previously seen total.

sums = defaultdict()
sums[0] = head

node  = head
total = 0
while node:
    total += node.val
    sums[total] = node.next
    node = node.next

Key aspects of this segment include the initialization of the dictionary with a zero sum pointing to the original head, which ensures that a zero-sum prefix at the very start of the list can be detected. The use of defaultdict allows the dictionary to be created without specifying a default factory, relying on explicit assignments only.

Second Traversal - Reconstructing the List

The second pass creates a dummy node (prehead) to simplify edge-case handling and then iterates through the list again, this time using the previously built map to skip over zero-sum intervals. By setting node.next to the stored successor for the current cumulative sum, the algorithm effectively removes any intervening nodes whose values collectively sum to zero.

prehead = node = ListNode()
total = 0
while node:
    total += node.val
    node.next = sums[total]
    node = node.next

The dummy node ensures that the method can return prehead.next safely even when the entire original list is eliminated. The loop’s logic mirrors the first traversal, guaranteeing that the same cumulative sums are encountered in the same order, which is essential for correctly applying the stored jump pointers.

Edge Cases Handled

When the input list is empty, the initial dictionary entry for sum zero points to None, and both traversals terminate immediately, resulting in a None return value. If the list consists of a single node whose value is zero, the first pass records a sum of zero mapping to None, and the second pass rewires the dummy node’s next to None, effectively removing the sole element. Situations where multiple overlapping zero-sum sublists exist are also covered because the dictionary always retains the latest occurrence of each sum, allowing the second pass to skip the longest possible zero-sum segment at each step.

Performance Optimizations

The algorithm achieves linear time behavior by avoiding nested loops; each node is visited exactly twice. Storing only the most recent occurrence of each cumulative sum eliminates the need for additional scans to locate the appropriate jump point. The use of a dummy head removes conditional checks for head manipulation, streamlining pointer updates. By reusing the same total variable across both passes, the code minimizes auxiliary storage, relying solely on the hash map to retain necessary state. This combination of a single hash table and two straightforward passes yields an efficient solution for the zero-sum sublist removal problem.

Imagine a long train track made of many numbered cars. Some cars have positive numbers, and some have negative numbers that act like holes sucking the value away. The goal is to find groups of cars sitting next to each other that add up to zero, because if they equal zero, they are just extra weight that can be removed entirely.

The computer starts by walking along the train track and keeping a running tally of the numbers as it visits each car. It plays a game of memory where it remembers the very last spot it saw a specific total number on a map. If it sees the same total twice, it knows that everything between those two spots adds up to exactly zero.

After it finishes walking the track the first time, it goes back to the beginning to rebuild the train. This time, whenever it hits a total it has seen before, it skips over all the middle cars and jumps straight to the end of where that group used to be. It keeps doing this until it reaches the end of the line, leaving behind a new, shorter train that has no hidden secrets adding up to nothing. By the time it finishes, all the junk has been cleared away, leaving only the cars that actually make the train move.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python	C++		Java					TS
	WalkCCC	Python	C++		Java
	leetcode.ca	Python	C++		Java		Go		Rust	TS
	Progiez	Python	C++		Java
github	black-shadows		C++
	charles-wangkai				Java
	everthis			JS
	fartem					Ruby
	fpdjsns		C++
	fsq		C++
	halfrost						Go
	JoshCrozier			JS
	lkwq007	Python
	pruthvikp	Python
	suxrobGM							C#
	trung-hn	Python
	varunu28				Java
	YuriSpiridonov	Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
pruthvikp	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality