给你一个链表的头节点 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
.
方法一:前缀和 + 哈希表
若链表节点的两个前缀和相等,说明两个前缀和之间的连续节点序列的和为
我们第一次遍历链表,用哈希表
接下来,我们再次遍历链表,若当前节点
最后返回链表的头节点
时间复杂度
# 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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0, head);
Map<Integer, ListNode> last = new HashMap<>();
int s = 0;
ListNode cur = dummy;
while (cur != null) {
s += cur.val;
last.put(s, cur);
cur = cur.next;
}
s = 0;
cur = dummy;
while (cur != null) {
s += cur.val;
cur.next = last.get(s).next;
cur = cur.next;
}
return dummy.next;
}
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
ListNode* dummy = new ListNode(0, head);
unordered_map<int, ListNode*> last;
ListNode* cur = dummy;
int s = 0;
while (cur) {
s += cur->val;
last[s] = cur;
cur = cur->next;
}
s = 0;
cur = dummy;
while (cur) {
s += cur->val;
cur->next = last[s]->next;
cur = cur->next;
}
return dummy->next;
}
};
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeZeroSumSublists(head *ListNode) *ListNode {
dummy := &ListNode{0, head}
last := map[int]*ListNode{}
cur := dummy
s := 0
for cur != nil {
s += cur.Val
last[s] = cur
cur = cur.Next
}
s = 0
cur = dummy
for cur != nil {
s += cur.Val
cur.Next = last[s].Next
cur = cur.Next
}
return dummy.Next
}
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function removeZeroSumSublists(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0, head);
const last = new Map<number, ListNode>();
let s = 0;
for (let cur = dummy; cur; cur = cur.next) {
s += cur.val;
last.set(s, cur);
}
s = 0;
for (let cur = dummy; cur; cur = cur.next) {
s += cur.val;
cur.next = last.get(s)!.next;
}
return dummy.next;
}