前往
大廳
主題

LeetCode - 82. Remove Duplicates from Sorted List II 解題心得

Not In My Back Yard | 2021-06-14 00:00:04 | 巴幣 0 | 人氣 392

題目連結:


題目意譯:
給定一個已排序的連結串列(Linked List)之開頭節點 head,刪除掉所有有著重複數字的節點,只留下原始串列中與其他數字相異的數字。請將串列排序後回傳。

限制:
串列中的節點數位於範圍 [0, 300] 中。
-100 ≦ Node.val ≦ 100
給定的串列保證按照升序排列。



範例測資:
範例 1:
輸入: head = [1,2,3,3,4,4,5]
輸出: [1,2,5]

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


解題思維:
這題的解法稍作變化即可。因為本題不是將重複的元素刪到剩一個留著,而是全數刪除。因此本來非空的串列有可能會被刪個精光。

因此,可以宣告一個用來當作「假的開頭」之節點(Dummy),然後讓 dummy 作為目前串列的頭(所以 dummy->next 要指向原本的 head)。

接著也是利用一個指標指向目前剩下的節點可以銜接的位置(一開始指向 dummy,代表 dummy 後面可以接東西)、另外兩個指標,一個用來存當前掃到的節點、一個用來存連續出現的節點值的開頭節點,以及一個用來統計節點值連續出現次數之變數。

剩下的就是按照類似原先的作法即可




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

創作回應

更多創作