鍊表應用: 簡化鏈結串列 Remove Zero Sum Nodes_Leetcode #1171

JJ Ying on Unsplash

題目敘述

題目會給定一個鏈結串列的起始點，要求我們把其中區間總和為0的部分刪除掉。

例如

1→ 2 → -2 → 3 → 4

裡面有一段是2 → -2 區間總和為零，所以簡化刪除後變成

1→ 3 → 4

題目的原文敘述

測試範例

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.

鏈結串列的節點總數目介於1~1000。

• Each node in the linked list has -1000 <= node.val <= 1000.

節點值都介於-1000 ~ 1000之間。

演算法 前綴和 + 字典

這題會用到以前學過的前綴和技巧。

從左到右滾動依序計算前綴和，並且把每個前綴和對應的節點存到字典裡面。

如果當下在某個位置前綴和為S，而且在字典裡面又發現前面曾經看過前綴和S，
那麼代表從前面到現在這個位置，區間的區間總和恰為0。

舉個實際的例子幫助讀者理解

假設輸入為 1 → 2 → -2 → 3 → 4

前綴和分別為

1, 3, 1, 4, 8

前綴和1看過兩次，代表區間 2 → -2 的區間節點總和為0，也就是我們要簡化刪除的地方。

簡化之後，新的鏈結串列變成

1→ 3 → 4

示意圖

image.png

程式碼 前綴和 + 字典

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:

        # DummyHead makes zero sum handling easier
        dummyHead = ListNode(0, head)

        # prefix sum so far
        prefixSum = 0

        ## Dictionay:
        # key: prefix sum
        # value: right most node who has this prefix sum
        rightMost = {0: dummyHead}

        # Update right most position for each prefix sum
        cur = head
        while cur:
            prefixSum += cur.val
            rightMost[prefixSum] = cur
            cur = cur.next

        
        # Skip and connect to right most position for already know prefix sum
        cur, prefixSum = dummyHead, 0
        while cur:
            prefixSum += cur.val
            junction = rightMost.get(prefixSum, cur)
            cur.next = junction.next
            cur = cur.next
        
        return dummyHead.next  

複雜度分析 前綴和 + 字典

時間複雜度:

線性掃描兩次，所需時間為O(n)。

空間複雜度:

需要建立一個前綴和字典，所需空間為O(n)。

關鍵知識點

同樣的前綴和若出現兩次以上，代表存在有區間總和為0的區間。

Reference:

[1] Remove Zero Sum Consecutive Nodes from Linked List - LeetCode