前往
大廳
主題

LeetCode - 1171. Remove Zero Sum Consecutive Nodes from Linked List 解題心得

Not In My Back Yard | 2024-05-18 12:00:06 | 巴幣 0 | 人氣 27

題目連結:


題目意譯:
給定一個連結串列(Linked List)的開頭節點 head,我們將重複地刪掉加總為 0 的連續序列直到找不到這樣子的序列為止。

做完刪除的動作之後,回傳最終的連結串列之開頭節點。你可以回傳任意一個可能的答案。

限制:
給定的連結串列會包含 1 到 1000 個節點。
連結串列中的每一個節點滿足 -1000 ≦ node.val(即節點值) ≦ 1000。



範例測資:
(注意到下列的範例中,所有序列為物件 ListNode 的序列化(Serializations)結果。)
範例 1:
輸入: head = [1,2,-3,3,1]
輸出: [3,1]
注: [1,2,1] 的答案也會被接受。

範例 2:
輸入: head = [1,2,3,-3,4]
輸出: [1,2,4]

範例 3:
輸入: head = [1,2,3,-3,-2]
輸出: [1]


解題思維:
核心思想可以參見這題,也就是說如果現在從頭加到當前節點 y 的總和在「之前」(假設先前滿足此總和的節點為 x)有出現過,則代表著 x(不含)~ y(含)之間的節點值總和恰好為 0(雖然該題當初是在討論餘數以及倍數,但是想法是類似的)。進而代表著 x(不含)~ y(含)之間的所有節點都可以根據題目的操作來刪除掉。

因此我們只需要一個雜湊表(Hash Table)來紀錄這些總和值以及總和值發生的節點。如果現在位於節點 y,一旦遇到當前總和值出現過(假設先前在節點 x)則從 x 開始「之後」才出現的總和值需要從雜湊表刪掉。不然之後出現一樣的總和值時,會誤刪不必要的,因為 x(不含)~ y(含)這一段已經被處理過了。

所以我們可以從 x 的下一個節點開始一個一個加總並處理這些「新來」的總和值直到碰到 y 為止。接著讓 x 的 next 指標指向 y 的下一個節點,即令 x->next = y->next,即可完成刪除的動作。

掃完所有節點之後便完成了刪除的動作。



而因為原本的開頭可能也會被刪除,因此我們可以用一個充數用的節點 dummy 來指向一開始給定的 head。最後只要回傳 dummy 指向的下一個節點即是新的開頭。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作