1171. 从链表中删去总和值为零的连续节点
给你一个链表的头节点 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.原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 3.6 MB, 提交时间: 2023-06-01 10:00:38
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeZeroSumSublists(head *ListNode) *ListNode {
dummy := &ListNode{Val : 0, Next : head}
sum := 0
dict := make(map[int]*ListNode)
for p := dummy; p != nil; p = p.Next {
sum += p.Val
dict[sum] = p
}
sum = 0
for p := dummy; p != nil; p = p.Next {
sum += p.Val
p.Next = dict[sum].Next
}
return dummy.Next
}
golang 解法, 执行用时: 0 ms, 内存消耗: 3.6 MB, 提交时间: 2023-06-01 10:00:21
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeZeroSumSublists(head *ListNode) *ListNode {
//添加一个哑结点防止头结点被删除等复杂情况
dummy := &ListNode{Val :0, Next : head}
sum := 0
//创建一个存储节点和sum的哈希表
HasMap := make(map[int]*ListNode)
for p := dummy; p != nil; p = p.Next {
//将每个节点的值进行累加
sum += p.Val
//本节点及其前面节点的val累加值放入key
//用一个hash表map来存储每个结点的前缀和，如果有前缀和相等的节点自动覆盖为后面的节点
HasMap[sum] = p
}
sum2 := 0
for p := dummy; p != nil; p = p.Next {
sum2 += p.Val
//哈希表里存的这个sum 肯定是第二次出现的
p.Next = HasMap[sum2].Next
}
return dummy.Next
}
java 解法, 执行用时: 2 ms, 内存消耗: 42 MB, 提交时间: 2023-06-01 09:59:51
/**
* 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);
dummy.next = head;
Map<Integer, ListNode> map = new HashMap<>();
// 首次遍历建立 节点处链表和<->节点 哈希表
// 若同一和出现多次会覆盖，即记录该sum出现的最后一次节点
int sum = 0;
for (ListNode d = dummy; d != null; d = d.next) {
sum += d.val;
map.put(sum, d);
}
// 第二遍遍历 若当前节点处sum在下一处出现了则表明两结点之间所有节点和为0 直接删除区间所有节点
sum = 0;
for (ListNode d = dummy; d != null; d = d.next) {
sum += d.val;
d.next = map.get(sum).next;
}
return dummy.next;
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 42.1 MB, 提交时间: 2023-06-01 09:58:59
/**
* 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);
dummy.next = head;
ListNode p = dummy;
//----某个presum_val最右侧的结点
Map<Integer, ListNode> presum_right_node = new HashMap<>();
int cur_presum = 0;
while (p != null) {
cur_presum += p.val;
presum_right_node.put(cur_presum, p);
p = p.next;
}
//----尽可能的往右删。
p = dummy;
cur_presum = 0;
while (p != null) {
cur_presum += p.val;
p.next = presum_right_node.get(cur_presum).next;
p = p.next;
}
return dummy.next;
}
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 11.1 MB, 提交时间: 2023-06-01 09:58:29
/**
* 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)
{
unordered_map<int, ListNode*> presum_lastNode_dic; //等于这个前缀和的最右一个的结点
ListNode * dummy = new ListNode(0);
dummy->next = head;
ListNode* p = dummy;
int cur_sum = 0;
while (p)
{
cur_sum += p->val;
presum_lastNode_dic[cur_sum] = p; //初始化字典（map）
p = p->next;
}
p = dummy;
cur_sum = 0;
while (p)
{
cur_sum += p->val;
p->next = presum_lastNode_dic[cur_sum] -> next; //2个点的presum相同====中间数字和为0 或者只有自己1个点
p = p->next;
}
return dummy->next;
}
};
python3 解法, 执行用时: 56 ms, 内存消耗: 16.4 MB, 提交时间: 2023-06-01 09:58:10
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
#（一）前缀和+无序字典
# 1.就一个套路sum[i:j] = presum[j] - presum[i]
# 2.list删除结点非常简单 把链接断了就ok
# 3.提速比较好的方式之一就是用hash
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
presum_lastNode_dic = defaultdict(ListNode)
dummy = ListNode(0)
dummy.next = head
p = dummy
cur_presum = 0
while p:
cur_presum += p.val
presum_lastNode_dic[cur_presum] = p #等于这去个前缀和的最右的一个结点
p = p.next
cur_presum = 0
p = dummy
while p:
cur_presum += p.val
p.next = presum_lastNode_dic[cur_presum].next #2个结点中间，都直接删除了 要么就只有自己1个结点
p = p.next
return dummy.next