What is the approach for solving the 'Remove Zero Sum Consecutive Nodes from Linked List' problem?

The solution involves iterating through the linked list while tracking cumulative sums using a hash map, adjusting pointers when zero-sum sequences are detected.

Can the problem have multiple valid outputs?

Yes, depending on which zero-sum sequences are removed, multiple valid outputs are possible, as long as all zero-sum nodes are excluded from the result.

What is the time complexity of the solution?

The time complexity is O(n), where n is the number of nodes in the linked list, as the list is traversed once.

How does the hash map help in solving this problem?

The hash map stores cumulative sums as we traverse the list. When the same sum appears again, it indicates a zero-sum sequence, which can be removed efficiently.

What are some common pitfalls when solving this problem?

Common mistakes include failing to update pointers correctly, not handling edge cases like empty lists, or misusing the hash map to track sums.

#1171

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

从链表中删去总和值为零的连续节点

给你一个链表的头节点 head ，请你编写代码，反复删去链表中由总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。删除完毕后，请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）示例 1：…

哈希表链表

题目描述

给你一个链表的头节点 head，请你编写代码，反复删去链表中由总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

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

示例 1：

输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。

示例 2：

输入：head = [1,2,3,-3,4]
输出：[1,2,4]

示例 3：

输入：head = [1,2,3,-3,-2]
输出：[1]

提示：

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

lightbulb

解题思路

方法一：前缀和 + 哈希表

若链表节点的两个前缀和相等，说明两个前缀和之间的连续节点序列的和为 $0$ ，那么可以消去这部分连续节点。

我们第一次遍历链表，用哈希表 $last$ 记录前缀和以及对应的链表节点，对于同一前缀和 $s$ ，后面出现的节点覆盖前面的节点。

接下来，我们再次遍历链表，若当前节点 $cur$ 的前缀和 $s$ 在 $last$ 出现，说明 $cur$ 与 $last[s]$ 之间的所有节点和为 $0$ ，我们直接修改 $cur$ 的指向，即 $cur.next = last[s].next$ ，这样就删去了这部分和为 $0$ 的连续节点。继续往后遍历，删除所有和为 $0$ 的连续节点。

最后返回链表的头节点 $dummy.next$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为链表的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        last = {}
        s, cur = 0, dummy
        while cur:
            s += cur.val
            last[s] = cur
            cur = cur.next
        s, cur = 0, dummy
        while cur:
            s += cur.val
            cur.next = last[s].next
            cur = cur.next
        return dummy.next

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate understanding of linked-list traversal and pointer manipulation.
question_mark
Look for the ability to optimize using a hash map to track sums efficiently.
question_mark
Evaluate how well the candidate handles edge cases such as lists with no zero-sum sequences or lists that are completely zero-sum.

warning

常见陷阱

外企场景

error
Failing to properly update pointers when removing zero-sum sequences, leading to lost nodes.
error
Overlooking edge cases like empty lists or lists without any zero-sum sequences.
error
Misusing the hash map to track sums, which can cause incorrect removal of nodes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Using a different approach for removing zero-sum sequences, such as a stack-based solution.
arrow_right_alt
Handling cases where the linked list contains only one node or very small lists.
arrow_right_alt
Returning multiple possible outputs based on how the zero-sum sequences are removed.

help

常见问题

外企场景

继续练习

#817 链表组件 #706 设计哈希映射 #705 设计哈希集合