Leetcode 1171: Remove Zero Sum Consecutive Nodes from Linked List
Given the head of a linked list, iteratively remove all consecutive subsequences of nodes whose sum is 0. Return the modified linked list after all such subsequences have been removed. You may return any valid result.
Problem
Approach
Steps
Complexity
Input: The input is the head of a singly linked list.
Example: Input: head = [2,-2,3,1,-1,4,-4,5]
Constraints:
• 1 <= length of linked list <= 1000
• -1000 <= node.val <= 1000
Output: Return the head of the modified linked list with all zero-sum subsequences removed.
Example: Output: [5]
Constraints:
• The output linked list should not contain any zero-sum consecutive subsequences.
Goal: Iteratively remove zero-sum consecutive subsequences from the linked list.
Steps:
• 1. Create a dummy node and link it to the head of the list.
• 2. Traverse the list while maintaining a prefix sum.
• 3. Use a hash map to track nodes corresponding to each prefix sum.
• 4. When a prefix sum is encountered again, remove all nodes in the subsequence between the two occurrences.
• 5. Return the updated list starting from the dummy node’s next pointer.
Goal: The input linked list contains integer values, and the removal should preserve non-zero-sum segments.
Steps:
• Each node's value lies in the range [-1000, 1000].
• The length of the list is between 1 and 1000.
Assumptions:
• Input is always a valid singly linked list.
• Zero-sum subsequences can span multiple nodes.
• Input: Input: head = [1,3,-3,4,5,-4]
• Explanation: The sequence [3,-3] sums to 0 and is removed. Then [4,5,-4] sums to 0 and is also removed. The final list is [1].
• Input: Input: head = [2,3,-5,5,-2,1]
• Explanation: The sequence [2,3,-5] sums to 0. Removing it leaves [5,-2,1]. No further zero-sum sequences exist. The result is [5,-2,1].
Approach: Use a prefix sum and a hash map to efficiently detect and remove zero-sum subsequences in a single traversal.
Observations:
• Using prefix sums allows quick identification of zero-sum subsequences.
• A hash map can store references to nodes corresponding to each prefix sum.
• Removing nodes in-place avoids unnecessary space usage and preserves the list structure.
Steps:
• 1. Initialize a dummy node pointing to the head of the list.
• 2. Maintain a running prefix sum as nodes are traversed.
• 3. Use a hash map to store the most recent occurrence of each prefix sum.
• 4. If a prefix sum repeats, all nodes between the previous occurrence and the current node sum to 0 and can be removed.
• 5. Adjust pointers to bypass the zero-sum segment.
Empty Inputs:
• An empty list returns an empty list.
Large Inputs:
• A list with 1000 nodes processes efficiently using prefix sums.
Special Values:
• Lists with all nodes summing to 0 should return an empty list.
Constraints:
• Negative and positive values should be handled correctly.
ListNode* removeZeroSumSublists(ListNode* head) {
ListNode* dummy = new ListNode(0), *cur = dummy;
dummy->next= head;
int prefix = 0;
map<int, ListNode*> mp;
while(cur) {
prefix += cur->val;
if(mp.count(prefix)) {
cur = mp[prefix]->next;
int p = prefix + cur->val;
while(p != prefix) {
mp.erase(p);
cur = cur->next;
p += cur->val;
}
mp[prefix]->next = cur->next;
} else mp[prefix] = cur;
cur = cur->next;
}
return dummy->next;
}
1 : Function Definition
ListNode* removeZeroSumSublists(ListNode* head) {
Define the function `removeZeroSumSublists`, which takes a `ListNode* head` as input and returns a `ListNode*` after removing any sublist with a sum of zero.
2 : Variable Initialization
ListNode* dummy = new ListNode(0), *cur = dummy;
Initialize a dummy node to simplify list manipulation and set `cur` to point to the dummy node.
3 : Variable Initialization
dummy->next = head;
Set the `next` pointer of the dummy node to point to the head of the input linked list.
4 : Variable Initialization
int prefix = 0;
Initialize the variable `prefix` to 0 to keep track of the prefix sum of node values.
5 : Variable Initialization
map<int, ListNode*> mp;
Initialize a map `mp` to store the first occurrence of each prefix sum and its corresponding node.
6 : Loop
while(cur) {
Start a while loop that iterates through the linked list until `cur` is null.
7 : Prefix Sum Calculation
prefix += cur->val;
Update the prefix sum by adding the value of the current node.
8 : Conditional
if(mp.count(prefix)) {
Check if the prefix sum has already been encountered in the map `mp`.
9 : Pointer Update
cur = mp[prefix]->next;
Set `cur` to the node right after the node corresponding to the previous occurrence of the same prefix sum.
10 : Variable Initialization
int p = prefix + cur->val;
Initialize `p` with the sum of `prefix` and the value of the current node.
11 : Loop
while(p != prefix) {
Start a loop to erase any prefix sums between the first occurrence and the current node, effectively removing the nodes in the zero-sum sublist.
12 : Map Operation
mp.erase(p);
Erase the prefix sum `p` from the map `mp`.
13 : Pointer Update
cur = cur->next;
Move the `cur` pointer to the next node in the list.
14 : Prefix Sum Calculation
p += cur->val;
Update the value of `p` by adding the value of the current node.
15 : Loop
}
End the loop for erasing nodes between the two prefix sums.
16 : Pointer Update
mp[prefix]->next = cur->next;
Update the `next` pointer of the node corresponding to the previous prefix sum to skip over the zero-sum sublist.
17 : Map Operation
} else mp[prefix] = cur;
If the prefix sum is not found in the map, store the current node in the map with the prefix sum as the key.
18 : Pointer Update
cur = cur->next;
Move the `cur` pointer to the next node.
19 : Return Statement
return dummy->next;
Return the next node after the dummy node, which represents the head of the modified linked list.
Best Case: O(N)
Average Case: O(N)
Worst Case: O(N)
Description: Each node is processed once, with hash map operations taking constant time.
Best Case: O(1)
Worst Case: O(N)
Description: Space complexity is proportional to the number of unique prefix sums in the worst case.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus