題目連結:
題目意譯:
你被給定一個連結串列(Linked List)的開頭節點 head,該串列包含著以若干個 0 作為間隔的一個整數序列。連結串列的開頭以及結尾都會有著節點值 == 0。
對於每兩個連續的 0,將它們之間的節點全部合併成單一一個節點,且其值為所有被合併的節點之值的總和。修改後的串列不應包含任何的 0。
回傳修改後的連結串列之開頭節點。
限制:
串列中的節點數位於範圍 [3, 2 × 10 ^ 5] 中。
0 ≦ Node.val ≦ 1000
沒有兩個連續的節點有著節點值 == 0。
連結串列的開頭以及結尾有著節點值 == 0。
範例測資:
範例 1:
輸入: head = [0,3,1,0,4,5,2,0]
輸出: [4,11]
解釋:
上圖代表著給定的連結串列。修改後的串列包含著
- 標以綠色的節點之總和:3 + 1 = 4。
- 標以紅色的節點之總和:4 + 5 + 2 = 11。
範例 2:
輸入: head = [0,1,0,3,0,2,2,0]
輸出: [1,3,4]
解釋:
上圖代表著給定的連結串列。修改後的串列包含著
- 標以綠色的節點之總和:1 = 1。
- 標以紅色的節點之總和:3 = 3。
- 標以黃色的節點之總和:2 + 2 = 4。
解題思維:
基於與
這題類似的原因,我們可以先宣告一個假的節點 dummy 來當作合併後的串列之開頭(暫時性的)。因為這樣之後的節點可以直接接在最後面而不用判斷當前串列是否為空。
接著就是直接掃過整個串列(可以直接忽略第一個節點,因為其值是 0),遇到非 0 的節點就加到當前的總和 S(一開始 S 為 0);遇到節點值為 0 的就新增一個節點值為 S 的到新串列(dummy 所在的那一個)的最尾端,然後將 S 歸零。
這樣便可以把每兩個 0 之間的節點值合併加總成單一一個節點。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。