Remove every contiguous segment of a linked list whose node values sum to zero, and return the cleaned list.
Remove Zero-Sum Consecutive Nodes From Linked List
You are given the head of a singly linked list. Repeatedly remove any contiguous sequence of nodes whose values add up to 0. Continue until no such sequence remains, then return the final head of the list.
A zero-sum segment can appear anywhere in the list, and removing one segment may create new zero-sum segments that also need to be eliminated.
Your task is to return the linked list after all zero-sum consecutive segments have been removed.
Notes
- The relative order of the remaining nodes must be preserved.
- If the entire list is removed, return an empty list.
- Node values may be positive, negative, or zero.
Input Format
- The input is the head of a singly linked list.
- Each node contains an integer value.
- The list length and value bounds are not specified here; assume standard interview-style constraints.
Output Format
- Return the head of the linked list after removing all zero-sum consecutive segments.
Constraints
- Preserve node order among remaining nodes.
- Remove all contiguous subsequences whose sum is
0. - If no such subsequence exists, return the original list unchanged.
Example 1
Input
head = [1, 2, -3, 3, 1]
Output
[3, 1]
Explanation
The segment [1, 2, -3] sums to 0, so it is removed. The remaining list is [3, 1].
Example 2
Input
head = [1, 2, 3, -3, 4]
Output
[1, 2, 4]
Explanation
The segment [3, -3] sums to 0 and is removed.
Show 1 more example
Example 3
Input
head = [1, 2, -3, 3, -3]
Output
[]
Explanation
[1, 2, -3] sums to 0, leaving [3, -3], which also sums to 0.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.