给你一个链表的头节点 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.
方法一：哈希表
给你一个链表的头节点 head，反复删去链表中总和值为 0 的连续节点组成的序列。
建立一个 dummy 节点，指向 head，节点值为 0。遍历一遍链表，同时记录前缀和，以当前前缀和为 key，当前节点为 value，存入哈希表中。如果相同前缀和已经存在，就可以直接覆盖掉原有节点。
第二遍重新遍历链表，同时记录前缀和 prefix，哈希表中对应 prefix 的节点是最后一次出现相同前缀和的节点，我们将这个节点的下一个节点，赋值给当前节点的下一个节点，中间跳过的部分总和即为 0。
最后我们返回 dummy 节点的下一节点，作为新的头节点。注意满足题目要求的答案不唯一，可以返回任何满足题目要求的答案。
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
int prefix = 0;
unordered_map<int, ListNode*> seen;
for (ListNode* node = dummy; node; node = node->next) {
prefix += node->val;
seen[prefix] = node;
}
prefix = 0;
for (ListNode* node = dummy; node; node = node->next) {
prefix += node->val;
node->next = seen[prefix]->next;
}
return dummy->next;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
Map<Integer, ListNode> seen = new HashMap<>();
int prefix = 0;
for (ListNode node = dummy; node != null; node = node.next) {
prefix += node.val;
seen.put(prefix, node);
}
prefix = 0;
for (ListNode node = dummy; node != null; node = node.next) {
prefix += node.val;
node.next = seen.get(prefix).next;
}
return dummy.next;
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class Solution {
public ListNode RemoveZeroSumSublists(ListNode head) {
int prefix = 0;
ListNode dummy = new ListNode(0);
dummy.next = head;
Dictionary<int, ListNode> seen = new Dictionary<int, ListNode>();
seen[0] = dummy;
for (ListNode node = dummy; node != null; node = node.next) {
prefix += node.val;
seen[prefix] = node;
}
prefix = 0;
for (ListNode node = dummy; node != null; node = node.next) {
prefix += node.val;
node.next = seen[prefix].next;
}
return dummy.next;
}
}
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
prefix = 0
seen = {}
seen[0] = dummy = ListNode(0)
dummy.next = head
while head:
prefix += head.val
seen[prefix] = head
head = head.next
head = dummy
prefix = 0
while head:
prefix += head.val
head.next = seen[prefix].next
head = head.next
return dummy.next
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| var removeZeroSumSublists = function(head) {
let dummy = new ListNode(0);
dummy.next = head;
let seen = {};
let prefix = 0;
for (let node = dummy; node !== null; node = node.next) {
prefix += node.val;
seen[prefix] = node;
}
prefix = 0;
for (let node = dummy; node !== null; node = node.next) {
prefix += node.val;
node.next = seen[prefix].next;
}
return dummy.next;
};
|
[sol1-Go]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func removeZeroSumSublists(head *ListNode) *ListNode {
dummy := &ListNode{Val: 0}
dummy.Next = head
seen := map[int]*ListNode{}
prefix := 0
for node := dummy; node != nil; node = node.Next {
prefix += node.Val
seen[prefix] = node
}
prefix = 0
for node := dummy; node != nil; node = node.Next {
prefix += node.Val
node.Next = seen[prefix].Next
}
return dummy.Next
}
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| typedef struct {
int key;
struct ListNode *val;
UT_hash_handle hh;
} HashItem;
HashItem *hashFindItem(HashItem **obj, int key) {
HashItem *pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry);
return pEntry;
}
bool hashAddItem(HashItem **obj, int key, const struct ListNode* val) {
if (hashFindItem(obj, key)) {
return false;
}
HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
pEntry->key = key;
pEntry->val = val;
HASH_ADD_INT(*obj, key, pEntry);
return true;
}
bool hashSetItem(HashItem **obj, int key, const struct ListNode* val) {
HashItem *pEntry = hashFindItem(obj, key);
if (!pEntry) {
hashAddItem(obj, key, val);
} else {
pEntry->val = val;
}
return true;
}
struct ListNode * hashGetItem(HashItem **obj, int key) {
HashItem *pEntry = hashFindItem(obj, key);
if (!pEntry) {
return NULL;
}
return pEntry->val;
}
void hashFree(HashItem **obj) {
HashItem *curr = NULL, *tmp = NULL;
HASH_ITER(hh, *obj, curr, tmp) {
HASH_DEL(*obj, curr);
free(curr);
}
}
struct ListNode* createListNode(int val) {
struct ListNode *obj = (struct ListNode *)malloc(sizeof(struct ListNode));
obj->val = val;
obj->next = NULL;
return obj;
}
struct ListNode* removeZeroSumSublists(struct ListNode* head) {
struct ListNode* dummy = createListNode(0);
dummy->next = head;
int prefix = 0;
HashItem *seen = NULL;
for (struct ListNode* node = dummy; node; node = node->next) {
prefix += node->val;
hashSetItem(&seen, prefix, node);
}
prefix = 0;
for (struct ListNode* node = dummy; node; node = node->next) {
prefix += node->val;
struct ListNode *curr = hashGetItem(&seen, prefix);
if (curr) {
node->next = curr->next;
}
}
hashFree(&seen);
struct ListNode* ret = dummy->next;
free(dummy);
return ret;
}
|
复杂度分析
时间复杂度：O(n)，其中 n 是链表的长度。
空间复杂度：O(n)，其中 n 是链表的长度。
