題目敘述
題目會給定一個鏈結串列的起始點，要求我們把其中區間總和為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
1and1000nodes.
鏈結串列的節點總數目介於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
