1171. Remove Zero Sum Consecutive Nodes from Linked List LeetCode Solution
In this guide, you will get 1171. Remove Zero Sum Consecutive Nodes from Linked List LeetCode Solution with the best time and space complexity. The solution to Remove Zero Sum Consecutive Nodes from Linked List problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Remove Zero Sum Consecutive Nodes from Linked List
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 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.
Complexity Analysis
Time Complexity:
Space Complexity:
1171. Remove Zero Sum Consecutive Nodes from Linked List LeetCode Solution in C++
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
ListNode dummy(0, head);
int prefix = 0;
unordered_map<int, ListNode*> prefixToNode;
prefixToNode[0] = &dummy;
for (; head; head = head->next) {
prefix += head->val;
prefixToNode[prefix] = head;
}
prefix = 0;
for (head = &dummy; head; head = head->next) {
prefix += head->val;
head->next = prefixToNode[prefix]->next;
}
return dummy.next;
}
}; /* code provided by PROGIEZ */
1171. Remove Zero Sum Consecutive Nodes from Linked List LeetCode Solution in Java
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0, head);
int prefix = 0;
Map<Integer, ListNode> 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;
}
} // code provided by PROGIEZ
1171. Remove Zero Sum Consecutive Nodes from Linked List LeetCode Solution in Python
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
dummy = ListNode(0, head)
prefix = 0
prefixToNode = {0: dummy}
while head:
prefix += head.val
prefixToNode[prefix] = head
head = head.next
prefix = 0
head = dummy
while head:
prefix += head.val
head.next = prefixToNode[prefix].next
head = head.next
return dummy.next # code by PROGIEZ
