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

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.

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

给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是前缀和。因为是找连续的node并且这些连续的node的sum是0，那么不难想到会是用前缀和做。我这里提供两种实现方式，一种扫描两遍，一种扫描一遍。时间空间复杂度都是O(n)。

首先是扫描两遍。第一遍是用hashmap记录好前缀和。前缀和的记录方式是<prefix sum, 最后一个ListNode>。对于每个不同的prefix sum，hashmap里记录的是最后一次出现这个前缀和的那个listnode。

第二遍再扫描的时候，如果遇到了一个出现在hashmap里的前缀和，那么就可以跳过整个那一段，因为那一段的listnode的sum一定是0。

Java实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        HashMap<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实现

/**
 * 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) {
        HashMap<Integer, ListNode> map = new HashMap<>();
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        int prefix = 0;
        while (cur != null) {
            prefix += cur.val;
            if (map.containsKey(prefix)) {
                cur = map.get(prefix).next;
                int p = prefix + cur.val;
                while (p != prefix) {
                    map.remove(p);
                    cur = cur.next;
                    p += cur.val;
                }
                map.get(prefix).next = cur.next;
            } else {
                map.put(prefix, cur);
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

LeetCode 题目总结