1171. 从链表中删去总和值为零的连续结点
给你一个链表的头结点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续结点组成的序列，直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头结点。
示例：
输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。
解题思路：
找到题目的关键点：和值为0的连续结点。我们来看看示例，如果我们选择[-3, 3]这个区间，那么从左至右累加各个结点的值在这个区间前后是没有变化的。也就是说，用list来表示链表的累加和：[1, 3, 0, 3, 4]，可以看到Node(2)和Node(3)处的累加和是相等的。这就是解题的关键，找到累加和不变的区间，让区间前一个Node的下一个Node等于区间结束后紧跟的下一个Node。
代码如下：
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
dummy.next = head
sumMap = {}
node = dummy
sum_node = 0
while node:
sum_node += node.val
sumMap[sum_node] = node
node = node.next
sum_node = 0
node = dummy
while node:
sum_node += node.val
node.next = sumMap[sum_node].next
node = node.next
return dummy.next
时间复杂度：O(N)，遍历结点；
空间复杂度：O(N) ，存储结点的累加和。
解法转自 Java HashMap 两次遍历即可
网友评论