题目描述
给你一个链表的头结点 head
,请你反复删去链表中由 总和 值为 0
的连续结点组成的序列,直到不存在这样的序列为止。
删除完毕后,请你返回最终结果链表的头结点。
你可以返回任何满足题目要求的答案。
(注意,下面示例中的所有序列,都是对 ListNode
对象序列化的表示。)
样例
输入:head = [1,2,-3,3,1]
输出:[3,1]
提示:答案 [1,2,1] 也是正确的。
输入:head = [1,2,3,-3,4]
输出:[1,2,4]
输入:head = [1,2,3,-3,-2]
输出:[1]
限制
- 给你的链表中可能有
1
到1000
个结点。 - 对于链表中的每个结点,结点的值:
-1000 <= node.val <= 1000
。
算法
(前缀和,哈希表) $O(n)$
- 大体思路为,我们从头开始遍历链表,记录当前的前缀和对应当前的结点。
- 如果发现当前的前缀和已经在哈希表中出现过了,则说明我们找到了一段总和
0
的连续子区间。 - 于是取出哈希表中的出现过的结点,然后再遍历到当前结点,遍历过程中,在哈希表中删除这些前缀和。更新链表。
- 最后继续从当前结点往后扫描。
- 在实现时,我们可以在头结点前加一个
dummy
结点方便操作。
时间复杂度
- 哈希表的操作时间复杂度为常数,每个位置最多被遍历两次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要额外 $O(n)$ 的空间存储哈希表。
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
ListNode *dummy = new ListNode(0);
dummy -> next = head;
bool found = false;
unordered_map<int, ListNode*> vis;
int sum = 0;
for (auto cur = dummy; cur != NULL; cur = cur -> next) {
sum += cur -> val;
if (vis.find(sum) != vis.end()) {
auto start = vis[sum];
int tmp_sum = sum;
for (auto t = start -> next; t != cur; t = t -> next) {
tmp_sum += t -> val;
vis.erase(tmp_sum);
}
start -> next = cur -> next;
} else {
vis[sum] = cur;
}
}
return dummy -> next;
}
};