1171. Remove Zero Sum Consecutive Nodes from Linked List #

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 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.

Problem Summary #

Given the head node head of a linked list, write code to repeatedly delete sequences of consecutive nodes in the linked list whose total sum is 0 until no such sequence exists. After the deletion is complete, return the head node of the final resulting linked list. You may return any answer that satisfies the problem requirements.

(Note that all sequences in the examples below are serialized representations of ListNode objects.)

Notes:

The linked list given to you may contain 1 to 1000 nodes.
For each node in the linked list, the node’s value is: -1000 <= node.val <= 1000.

Solution Approach #

Given a linked list, remove all nodes in the linked list whose sum is 0.
Due to the characteristics of a linked list, random access is not possible. Therefore, scan from the head of the linked list toward the end and store the cumulative sum in a dictionary. When the same cumulative sum appears again, it means the segment in between sums to 0, so this segment should be deleted. During the deletion of this segment, the cumulative sums stored in the dictionary for this segment also need to be deleted. There is a special case to handle: if the total sum of the entire linked list is 0, then the final result is an empty linked list. To handle this special case, the value 0 is pre-stored in the dictionary.

Code #


package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// Solution 1
func removeZeroSumSublists(head *ListNode) *ListNode {
	// Calculate the cumulative sum; the sum is stored as the key in the map, and the value stores the pointer to that node. If a duplicate sum appears in the dictionary, it means a segment with sum 0 has appeared.
	sum, sumMap, cur := 0, make(map[int]*ListNode), head
	// Add the special value 0 to the dictionary to prevent the final linked list from being completely eliminated
	sumMap[0] = nil
	for cur != nil {
		sum = sum + cur.Val
		if ptr, ok := sumMap[sum]; ok {
			// A duplicate sum is found in the dictionary, meaning the segment between [ptr, tmp] has sum 0, and this is the segment to delete.
			// Also delete the sums of this middle segment from the map
			if ptr != nil {
				iter := ptr.Next
				tmpSum := sum + iter.Val
				for tmpSum != sum {
					// Delete the middle segment with sum 0; tmpSum continuously accumulates to delete the sums from the map
					delete(sumMap, tmpSum)
					iter = iter.Next
					tmpSum = tmpSum + iter.Val
				}
				ptr.Next = cur.Next
			} else {
				head = cur.Next
				sumMap = make(map[int]*ListNode)
				sumMap[0] = nil
			}
		} else {
			sumMap[sum] = cur
		}
		cur = cur.Next
	}
	return head
}

// Solution 2 Brute-force solution
func removeZeroSumSublists1(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	h, prefixSumMap, sum, counter, lastNode := head, map[int]int{}, 0, 0, &ListNode{Val: 1010}
	for h != nil {
		for h != nil {
			sum += h.Val
			counter++
			if v, ok := prefixSumMap[sum]; ok {
				lastNode, counter = h, v
				break
			}
			if sum == 0 {
				head = h.Next
				break
			}
			prefixSumMap[sum] = counter
			h = h.Next
		}
		if lastNode.Val != 1010 {
			h = head
			for counter > 1 {
				counter--
				h = h.Next
			}
			h.Next = lastNode.Next
		}
		if h == nil {
			break
		} else {
			h, prefixSumMap, sum, counter, lastNode = head, map[int]int{}, 0, 0, &ListNode{Val: 1010}
		}
	}
	return head
}