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

链接：1171.从链表中删去总和值为零的连续节点
难度：Medium
标签：哈希表、链表
简介：给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。删除完毕后，请你返回最终结果链表的头节点。

题解 1 - python

• 编辑时间：2023-06-11
• 执行用时：280ms
• 内存消耗：16.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
        h = ListNode()
        h.next = head
        sums = [1]
        p = h
        start = end = -1
        find = False
        while p.next and not find:
            sum = p.next.val + sums[-1]
            sums.append(sum)
            for i in range(len(sums) - 1):
                if sum - sums[i] == 0:
                    start = i
                    end = len(sums) - 1
                    find = True
                    break
            p = p.next
        if start == -1:
            return h.next
        p = h
        for i in range(start):
            p = p.next
        while end-start > 0:
            p.next = p.next.next
            end -= 1
        return self.removeZeroSumSublists(h.next)

题解 2 - cpp

• 编辑时间：2023-06-11
• 执行用时：40ms
• 内存消耗：12.1MB
• 编程语言：cpp
• 解法介绍：前缀和存储，每次找最前面可以组合为0的节点，递归删除节点。

class Solution {
public:
    ListNode *h = new ListNode();
    ListNode* removeZeroSumSublists(ListNode* head) {
        h->next = head;
        vector<int> sums(1, 0);
        auto p = h;
        int start = -1, end = -1;
        bool find = false;
        while (p->next && !find) {
            int sum = p->next->val + sums.back();
            sums.push_back(sum);
            for (int i = 0; i < sums.size() - 1; i++) {
                if (sum - sums[i] == 0) {
                    start = i;
                    end = sums.size() - 1;
                    find = true;
                    break;
                }
            }
            p = p->next;
        }
        if (start == -1) return h->next;
        p = h;
        for (int i = 0; i < start; i++) p = p->next;
        while (end - start > 0) p->next = p->next->next, end--;
        return removeZeroSumSublists(h->next);
    }
};

题解 3 - rust

• 编辑时间：2023-06-11
• 执行用时：8ms
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn remove_zero_sum_sublists(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut h = Box::new(ListNode::new(0));
        h.next = head;
        let mut sums = vec![1];
        let mut p = &mut h;
        let (mut start, mut end) = (usize::MAX, usize::MAX);
        let mut find = false;
        while p.next.is_some() && !find {
            let next = p.next.as_mut().unwrap();
            let sum = next.val + sums.last().unwrap();
            sums.push(sum);
            for i in 0..sums.len() - 1 {
                if sum - sums[i] == 0 {
                    start = i;
                    end = sums.len() - 1;
                    find = true;
                    break;
                }
            }
            p = next;
        }
        if start == usize::MAX {
            h.next
        } else {
            p = &mut h;
            for i in 0..start {
                p = p.next.as_mut().unwrap();
            }
            while end - start > 0 {
                let child = p.next.as_mut().unwrap().next.take();
                p.next = child;
                end -= 1;
            }
            Solution::remove_zero_sum_sublists(h.next)
        }
    }
}