[LeetCode] 1171. Remove Zero Sum Consecutive Nodes from Linked List

[grandyang]

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list.  You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:

• The given linked list will contain between 1 and 1000 nodes.
• Each node in the linked list has -1000 <= node.val <= 1000.

这道题让从一个链表中移除所有和为0的连续的结点，并给了好几个例子帮助我们理解题意。好久没玩链表的题了，对于一道 Medium 的题来说，应该不会太复杂。其实链表的问题都可以当成数组问题来思考，二者的区别的是链表不能像数组那样可以直接通过下标来访问元素，处理起来会麻烦一些。这道题可以看作是要找和为0的所有子数组，这里难道要遍历所有子数组求和么？对于数组可能还好，但对于链表来说简直是灾难，所以一定要用些技巧，这里要借助累加和来做，比如对于例子1来说 [1,2,-3,3,1]，建立累加和数组为 [1,3,0,3,4]，可以发现出现0了，这表示前面所有的数字之和一定为0。还可以发现出现了两个3，这表示中间的某个子数组之和为0了。再比如对于例子3来说 [1,2,3,-3,-2]，建立累加和数组为 [1,3,6,3,1]，可以发现，0不一定总会出现，但是一旦出现相同的数字，则表示一定有和为0的子数组出现，所以可以利用这个特点来快速定位子数组的位置进行操作。为了快速地找出重复，并且还需要记录位置，可以用 HashMap 来建立累加和跟其对应位置结点之间的映射。对于链表的题，基本上都需要建立一个 dummy 结点，将其 next 结点指向 head，因为 head 结点很有可能被移除掉。用 cur 结点来遍历链表，初始化指向 dummy 结点，用变量 curSum 来记录当前的累加和，初始化为0。开始遍历链表，将当前遍历到的结点值加到 curSum 中，若这个 curSum 已经在 HashMap 中出现了，表示已经有了和为0的连续结点，此时需要从 HashMap 中移除这些结点，将 cur 指向前一个累加和为 curSum 的结点位置的下一个结点，然后将该结点值加上 curSum 存入临时变量t中，若这个t不存在 HashMap 中，进行循环，从 HashMap 中移除t的映射对儿，然后 cur 指向下一个结点，t再加上下一个结点值继续循环。循环退出后，将 m[curSum] 结点的下一个位置指向 cur->next，这样就相当于跳过了和为0的所有连续结点。若 curSum 不在 HashMap 中，则建立 curSum 和结点 cur 之间的映射。最后返回 dummy->next 即可，参见代码如下：

解法一：

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        dummy->next = head;
        unordered_map<int, ListNode*> m;
        int curSum = 0;
        while (cur) {
            curSum += cur->val;
            if (m.count(curSum)) {
                cur = m[curSum]->next;
                int t = curSum + cur->val;
                while (t != curSum) {
                    m.erase(t);
                    cur = cur->next;
                    t += cur->val;
                }
                m[curSum]->next = cur->next;
            } else {
                m[curSum] = cur;
            }
            cur = cur->next;
        }
        return dummy->next;
    }
};

我们还可以通过两次遍历让写法更简洁一些，虽然没有上面的解法高效。但整体思路还是很像的，都是利用累加和相同来确定和为0的连续结点的位置，这里通过第一次遍历先建立累加和跟最后一次出现该累加和位置的结点的遍历，因为累加和可能会出现重复，后面的映射会覆盖前面的映射。这样在第二次遍历的时候，每次都用将 cur->next 赋值为 m[curSum]->next，那么遇到相同的累加和时，中间和为0的连续结点就被跳过了，实现了同样的目的，参见代码如下：

解法二：

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        unordered_map<int, ListNode*> m;
        int curSum = 0;
        for (ListNode *cur = dummy; cur; cur = cur->next) {
            m[curSum += cur->val] = cur;
        }
        curSum = 0;
        for (ListNode *cur = dummy; cur; cur = cur->next) {
            cur->next = m[curSum += cur->val]->next;
        }
        return dummy->next;
    }
};

Github 同步地址:

#1171

类似题目：

Delete N Nodes After M Nodes of a Linked List

参考资料：

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/discuss/366350/C%2B%2B-O(n)-(explained-with-pictures)

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/discuss/366319/JavaC%2B%2BPython-Greedily-Skip-with-HashMap

LeetCode All in One 题目讲解汇总(持续更新中...)