1171. 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.

题目大意

给你一个链表的头节点 head，请你编写代码，反复删去链表中由总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。删除完毕后，请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

提示：

给你的链表中可能有 1 到 1000 个节点。
对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.

解题思路

给出一个链表，要求把链表中和为 0 的结点都移除。
由于链表的特性，不能随机访问。所以从链表的头开始往后扫，把累加和存到字典中。当再次出现相同的累加和的时候，代表这中间的一段和是 0，于是要删除这一段。删除这一段的过程中，也要删除这一段在字典中存过的累加和。有一个特殊情况需要处理，即整个链表的总和是 0，那么最终结果是空链表。针对这个特殊情况，字典中先预存入 0 值。

代码


package leetcode

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

// 解法一
func removeZeroSumSublists(head *ListNode) *ListNode {
	// 计算累加和，和作为 key 存在 map 中，value 存那个节点的指针。如果字典中出现了重复的和，代表出现了和为 0 的段。
	sum, sumMap, cur := 0, make(map[int]*ListNode), head
	// 字典中增加 0 这个特殊值，是为了防止最终链表全部消除完
	sumMap[0] = nil
	for cur != nil {
		sum = sum + cur.Val
		if ptr, ok := sumMap[sum]; ok {
			// 在字典中找到了重复的和，代表 [ptr, tmp] 中间的是和为 0 的段，要删除的就是这一段。
			// 同时删除 map 中中间这一段的和
			if ptr != nil {
				iter := ptr.Next
				tmpSum := sum + iter.Val
				for tmpSum != sum {
					// 删除中间为 0 的那一段，tmpSum 不断的累加删除 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
}

// 解法二 暴力解法
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
}