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

这道题我不会。

参考做法

算法思想

设链表节点值依次为 a、b、c、d、e、f、g。

若a + b = m,且a + b + c + d = m。那么就可确定c + d = 0。

这样就找到了一组和为0的连续节点。

依据这样的思路，使用一个map集合，将每个节点和它以及之前节点的值的和一一对应起来。

也就是说，key为int，value为节点指针。

每个节点指针对应着：该节点及其之前所有结点的值的总和。

注意：key为int，也就是说，如果值相同，那么后面的节点指针会覆盖前面的节点指针。

并且头节点也可能被删除，所以需要添加哑节点。

链表和对应的map集合元素。

然后遍历链表，同时累加对应节点值，用sum表示。

设当前节点为node，那么node->next = map[sum]->next。

即：node对应的sum在map中只有两种情况：一是map中sum对应的节点是它自己，也就是node；二是对应的节点是它后面的某个节点(因为后面会覆盖前面的)，这说明：node的下一个节点一直到map中对应的节点，这段连续节点的值的总和是零。那么就应该删除掉这段节点。

这两种情况都能用上面这句代码表示。

对于第一种情况：这是个恒等式。

对于第二种情况：可以删除掉这段和为0的连续节点。

算法实现

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode * dummy = new ListNode(0);
        dummy->next = head;
        unordered_map<int, ListNode *> map;
        ListNode * node = dummy;
        int sum = 0;
        while (node != nullptr) {
            sum = sum + node->val;
            map[sum] = node;
            node = node->next;
        }
        node = dummy;
        sum = 0;
        while (node != nullptr) {
            sum = sum + node->val;
            node->next = map[sum]->next;
            node = node->next;
        }
        return dummy->next;
    }
};

性能分析

时间复杂度：遍历了两遍链表，$O(n)$。

空间复杂度：$O(n)$。