Remove Zero Sum Consecutive Nodes from Linked List solution and explanation
Google
9 more videos on this problem
Remove Zero Sum Consecutive Nodes from Linked List | Made Super Easy | Leetcode-1171codestorywithMIK · 23:53 · 21K views
LeetCode 1171 | Remove Zero Sum Consecutive Nodes from Linked Listleetuition · 12:39 · 16K views
1171. Remove Zero Sum Consecutive Nodes from Linked List | Prefix Sum | Brute -to- OptimalAryan Mittal · 34:42 · 5K views
1171 Remove zero sum consecutive nodes from linked list | leetcode daily challenge | DSA | ShashwatShashCode · 20:24 · 2K views
LeetCode 1171 | Remove Zero Sum Consecutive Nodes from Linked List | HashMap | PreSum | JavaSleepy Cracker · 7:55 · 1K views
Remove Zero Sum Consecutive Nodes from Linked List || LeetCode 1171DSA Solutions · 14:57 · 1K views
1171. Remove Zero Sum Consecutive Nodes from Linked List (Leetcode Medium)Programming Live with Larry · 42:16 · 721 views
LeetCode 1171 - Remove Zero Sum Consecutive Nodes From Linked List - PythonAlpha-Code · 12:43 · 450 views
1171. Remove Zero Sum Consecutive Nodes from Linked List | Prefix Sum + Hashing 🔥 | O(N) | C++Priyanshi Porwal · 20:43 · 309 views
Leetcode 1171: Remove Zero Sum Consecutive Nodes from Linked ListAlgorithms Casts · 18:33 · 269 views
The problem
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.
(Note that in the examples below, all sequences are serializations of ListNode objects.)
Example 1:
Input: head = [1,2,-3,3,1] Output: [3,1] Note: The answer [1,2,1] would also be accepted.
Example 2:
Input: head = [1,2,3,-3,4] Output: [1,2,4]
Example 3:
Input: head = [1,2,3,-3,-2] Output: [1]
Constraints:
- The given linked list will contain between
1and1000nodes. - Each node in the linked list has
-1000 <= node.val <= 1000.
Approach overview
Problem Overview: You are given the head of a linked list. If any consecutive sequence of nodes sums to 0, that entire sequence should be removed from the list. This removal can create new zero-sum sequences, so the process continues until no such segment exists.
Approach 1: Iterative Node Skipping (O(n²) time, O(1) space)
This approach repeatedly scans the list and checks every starting node to see whether a future sequence sums to zero. For each node, maintain a running sum while iterating forward. If the sum becomes 0, skip the entire range by adjusting the previous node’s next pointer. Because each node may trigger another forward scan, the algorithm can degrade to O(n²) time. The advantage is minimal memory usage since it only uses pointers and running sums without extra data structures. This approach helps you understand the mechanics of node removal in a linked list.
Approach 2: Prefix Sum Hash Map (O(n) time, O(n) space)
The optimal solution uses the prefix sum idea with a hash table. Traverse the list while maintaining a running prefix sum. If the same prefix sum appears twice, the nodes between those two positions must sum to zero. Store each prefix sum in a hash map pointing to the latest node where that sum appears. In a second pass, recompute prefix sums and update pointers so that each node skips directly to the next valid node stored in the map. This effectively removes all zero-sum segments in one sweep.
The key insight: identical prefix sums indicate a zero-sum range between them. Using a hash lookup reduces detection of these ranges to constant time, making the full traversal O(n). This pattern is common in problems involving cumulative sums and range detection, often discussed alongside hash map or linked list manipulations.
Recommended for interviews: The prefix sum + hash map approach is what most interviewers expect. The iterative method demonstrates that you understand linked list traversal and pointer manipulation, but the prefix-sum optimization shows stronger algorithmic thinking and familiarity with hash-based lookups that reduce quadratic scans to linear time.
Approach 1: Prefix Sum Hash Map
This approach uses a hashmap to record prefix sums while iterating through the linked list. When a prefix sum is repeated, it indicates that the nodes between the occurrences of the prefix sum form a zero-sum sequence.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
dummy.next = head
prefix_sum_map = {}
prefix_sum = 0
cur = dummy
while cur:
prefix_sum += cur.val
if prefix_sum in prefix_sum_map:
prev = prefix_sum_map[prefix_sum]
node = prev.next
p = prefix_sum
while node != cur:
p += node.val
del prefix_sum_map[p]
node = node.next
prev.next = cur.next
else:
prefix_sum_map[prefix_sum] = cur
cur = cur.next
return dummy.nextimport java.util.HashMap;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
HashMap<Integer, ListNode> map = new HashMap<>();
int prefix = 0;
for (ListNode cur = dummy; cur != null; cur = cur.next) {
prefix += cur.val;
if (map.containsKey(prefix)) {
cur = map.get(prefix).next;
int sum = prefix + cur.val;
while (sum != prefix) {
map.remove(sum);
cur = cur.next;
sum += cur.val;
}
map.get(prefix).next = cur.next;
} else {
map.put(prefix, cur);
}
}
return dummy.next;
}
}#include <unordered_map>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* removeZeroSumSublists(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
std::unordered_map<int, ListNode*> prefixSumMap;
int sum = 0;
for (ListNode* cur = dummy; cur != nullptr; cur = cur->next) {
sum += cur->val;
if (prefixSumMap.find(sum) != prefixSumMap.end()) {
ListNode* prev = prefixSumMap[sum];
ListNode* temp = prev->next;
int p = sum;
while (temp != cur) {
p += temp->val;
prefixSumMap.erase(p);
temp = temp->next;
}
prev->next = cur->next;
} else {
prefixSumMap[sum] = cur;
}
}
return dummy->next;
}function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function removeZeroSumSublists(head) {
let dummy = new ListNode(0);
dummy.next = head;
let prefixSumMap = new Map();
let prefix = 0;
for (let cur = dummy; cur !== null; cur = cur.next) {
prefix += cur.val;
if (prefixSumMap.has(prefix)) {
let node = prefixSumMap.get(prefix).next;
let sum = prefix;
while (node !== cur) {
sum += node.val;
prefixSumMap.delete(sum);
node = node.next;
}
prefixSumMap.get(prefix).next = cur.next;
} else {
prefixSumMap.set(prefix, cur);
}
}
return dummy.next;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeZeroSumSublists(struct ListNode* head) {
struct ListNode *dummy = malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = head;
struct ListNode *cur = dummy;
int prefix_sum = 0;
struct ListNode **seen = calloc(1001, sizeof(struct ListNode*));
seen[0] = dummy;
while (cur) {
prefix_sum += cur->val;
if (seen[prefix_sum]) {
struct ListNode *node = seen[prefix_sum]->next;
int p = prefix_sum;
while (node != cur) {
p += node->val;
seen[p] = NULL;
node = node->next;
}
seen[prefix_sum]->next = cur->next;
} else {
seen[prefix_sum] = cur;
}
cur = cur->next;
}
return dummy->next;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode RemoveZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
var prefixSumMap = new Dictionary<int, ListNode>();
int prefix = 0;
for (ListNode cur = dummy; cur != null; cur = cur.next) {
prefix += cur.val;
if (prefixSumMap.ContainsKey(prefix)) {
cur = prefixSumMap[prefix].next;
int sum = prefix + cur.val;
while (sum != prefix) {
prefixSumMap.Remove(sum);
cur = cur.next;
sum += cur.val;
}
prefixSumMap[prefix].next = cur.next;
} else {
prefixSumMap[prefix] = cur;
}
}
return dummy.next;
}
}In the Python solution, similar to others, a hashmap and a dummy node are used. The main loop calculates prefix sums and uses them to remove zero-sum subsequences.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 2: Iterative Node Skipping
This approach keeps processing the list until no zero-sum sublists can be found. This involves iterative rescanning of the list and skipping nodes accordingly.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeZeroSumSublists(self, head):
dummy = ListNode(0)
dummy.next = head
removed = True
while removed:
cur = dummy
sum = 0
removed = False
while cur.next:
sum += cur.next.val
if sum == 0:
cur.next = cur.next.next
removed = True
else:
cur = cur.next
return dummy.nextclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
boolean removed;
do {
ListNode cur = dummy;
int sum = 0;
removed = false;
while (cur.next != null) {
sum += cur.next.val;
if (sum == 0) {
cur.next = cur.next.next;
removed = true;
} else {
cur = cur.next;
}
}
} while (removed);
return dummy.next;
}
}#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* removeZeroSumSublists(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
bool removed = false;
do {
ListNode* cur = dummy;
int sum = 0;
removed = false;
while (cur->next) {
sum += cur->next->val;
ListNode* node = cur->next;
if (sum == 0) {
cur->next = node->next;
removed = true;
} else {
cur = cur->next;
}
}
} while (removed);
return dummy->next;
}function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function removeZeroSumSublists(head) {
let dummy = new ListNode(0);
dummy.next = head;
let removed = true;
while (removed) {
let cur = dummy;
let sum = 0;
removed = false;
while (cur.next !== null) {
sum += cur.next.val;
if (sum === 0) {
cur.next = cur.next.next;
removed = true;
} else {
cur = cur.next;
}
}
}
return dummy.next;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeZeroSumSublists(struct ListNode* head) {
struct ListNode dummy, *cur, *node, *prev;
int sum = 0, found;
dummy.next = head;
do {
found = 0;
cur = &dummy;
sum = 0;
while (cur->next) {
sum += cur->next->val;
node = cur->next;
if (sum == 0) {
cur->next = node->next;
found = 1;
} else {
cur = cur->next;
}
}
} while (found);
return dummy.next;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode RemoveZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
bool removed = true;
while (removed) {
ListNode cur = dummy;
int sum = 0;
removed = false;
while (cur.next != null) {
sum += cur.next.val;
if (sum == 0) {
cur.next = cur.next.next;
removed = true;
} else {
cur = cur.next;
}
}
}
return dummy.next;
}
}The Python approach executes an iterative removal of zero-sum sequences by setting a flag, removing nodes, and repeating until no changes are necessary.
Time Complexity: O(n^2).
Space Complexity: O(1).
Approach 3: Prefix Sum + Hash Table
If two prefix sums of the linked list are equal, it means that the sum of the continuous node sequence between the two prefix sums is 0, so we can remove this part of the continuous nodes.
We first traverse the linked list and use a hash table last to record the prefix sum and the corresponding linked list node. For the same prefix sum s, the later node overwrites the previous node.
Next, we traverse the linked list again. If the current node cur has a prefix sum s that appears in last, it means that the sum of all nodes between cur and last[s] is 0, so we directly modify the pointer of cur to last[s].next, which removes this part of the continuous nodes with a sum of 0. We continue to traverse and delete all continuous nodes with a sum of 0.
Finally, we return the head node of the linked list dummy.next.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function removeZeroSumSublists(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0, head);
const last = new Map<number, ListNode>();
let s = 0;
for (let cur = dummy; cur; cur = cur.next) {
s += cur.val;
last.set(s, cur);
}
s = 0;
for (let cur = dummy; cur; cur = cur.next) {
s += cur.val;
cur.next = last.get(s)!.next;
}
return dummy.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeZeroSumSublists(head *ListNode) *ListNode {
dummy := &ListNode{0, head}
last := map[int]*ListNode{}
cur := dummy
s := 0
for cur != nil {
s += cur.Val
last[s] = cur
cur = cur.Next
}
s = 0
cur = dummy
for cur != nil {
s += cur.Val
cur.Next = last[s].Next
cur = cur.Next
}
return dummy.Next
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn remove_zero_sum_sublists(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let dummy = Some(Box::new(ListNode { val: 0, next: head }));
let mut last = std::collections::HashMap::new();
let mut s = 0;
let mut p = dummy.as_ref();
while let Some(node) = p {
s += node.val;
last.insert(s, node);
p = node.next.as_ref();
}
let mut dummy = Some(Box::new(ListNode::new(0)));
let mut q = dummy.as_mut();
s = 0;
while let Some(cur) = q {
s += cur.val;
if let Some(node) = last.get(&s) {
cur.next = node.next.clone();
}
q = cur.next.as_mut();
}
dummy.unwrap().next
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum Hash Map | Time Complexity: O(n). Space Complexity: O(n). |
| Iterative Node Skipping | Time Complexity: O(n^2). Space Complexity: O(1). |
| Prefix Sum + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Node Skipping | O(n²) | O(1) | Useful for understanding pointer manipulation and when minimizing memory usage matters |
| Prefix Sum Hash Map | O(n) | O(n) | Best general solution. Detects zero-sum segments quickly using prefix sums and hash lookups |
Frequently asked questions
Is Remove Zero Sum Consecutive Nodes from Linked List easy or hard?
The problem is rated Medium because it combines linked list pointer manipulation with the prefix sum technique. Developers familiar with prefix sums in arrays often find the concept straightforward, but applying it to linked lists requires careful pointer updates.
Remove Zero Sum Consecutive Nodes from Linked List Python/Java solution
Most implementations follow the same prefix sum logic across languages. Traverse the list, store prefix sums in a hash map mapping sum to node, then adjust node pointers in a second pass. This approach translates directly to Python, Java, C++, C#, and JavaScript.
How to solve Remove Zero Sum Consecutive Nodes from Linked List in O(n)?
Maintain a running prefix sum while traversing the list and store each sum in a hash map mapped to its latest node. If a prefix sum repeats, the nodes between the two occurrences sum to zero. Updating the previous node's next pointer removes the entire segment, allowing the algorithm to complete in linear time.
What is the best approach for Remove Zero Sum Consecutive Nodes from Linked List?
The most efficient approach uses prefix sums with a hash map. While traversing the linked list, store the latest node for each prefix sum. If the same prefix sum appears again, the nodes between them sum to zero and can be removed by updating pointers. This runs in O(n) time with O(n) extra space.
Is Remove Zero Sum Consecutive Nodes from Linked List asked at Google/Amazon/Meta?
Linked list problems involving prefix sums and hash maps are common in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your ability to detect ranges using prefix sums and manipulate pointers efficiently in a linked list.
What data structure is used in Remove Zero Sum Consecutive Nodes from Linked List?
The optimal solution combines a linked list traversal with a hash map that stores prefix sums. The linked list handles node connections, while the hash map enables constant-time detection of previously seen sums to identify zero-sum ranges.
What is the time complexity of Remove Zero Sum Consecutive Nodes from Linked List?
The optimal prefix sum hash map solution runs in O(n) time because each node is processed a constant number of times. The space complexity is O(n) due to storing prefix sums in a hash map. A simpler iterative scanning approach exists but can take O(n²) time in the worst case.