0082. Remove Duplicates from Sorted List II (Medium)
Question
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example 1
| |
Example 2
| |
分析/解題
給定一個排序好的鏈結串列，將擁有重複的數字的節點全數刪去，
只保留原先在串列上相異的數字。
我們之前就嘗試過從鏈結串列刪去節點 的題目了，
只是今天這組更激進一點XD
原本是刪到剩一個即可，現在變成要將重複的全都刪掉，
那麼，該怎麼辦呢？
由於有可能刪到第一個，一般來說這種狀況，
習慣上會開出一個dummy node做為不會變動的節點參照，
我們先將其叫做dum，簡單將dum的next連接至head即可。
接下來要處理的是：我們要記得數值一致的節點群前面的那一個節點 ，
這樣刪去的時候才能將前後重新連接上。
因此，我們需要一個節點記錄，這裡將它叫做pre ；
另一個節點則做為迭代用，記錄現在所在的位置，將其稱做cur ，且就位置關係來說，pre的next應該會是cur 。
開始時pre的起始點 應該是dum ，這樣cur 會從head 開始，
當cur還沒走到底的時候要進行迴圈遍歷 。
另外在內部每次要迴圈檢查 ：
1. cur是否有下一個節點
且
2. cur的下一個節點和自己的值是否相等
(和先前一樣，這個迴圈用來略過所有重複值的節點 )
當走完以後有可能是
- cur還沒到底(有值) =>
pre的next就是cur ，所以再往下找的話要將pre設為pre.next - cur已經碰到底了 (cur.next == null) =>
將pre.next指向null (pre.next = cur.next)
最後，別忘了將cur往下走(cur = cur.next) 。
最終做完的時候，由於先前我們將dum.next設定成head ，
中間連接有變動的話，會被pre的操作給連接過去，
所以新的head的位置不管有無更動，
應該還是位於dum.next上。
(因為pre一開始等於dum，pre.next一開始會連動到dum.next )
依此，寫成程式碼。
Java
Java的部分不要忘記該new的dum，
剩下就只有判斷null的時候不像Python可以直接用if not，
其他大多大同小異；Python的邏輯是一致的，就不再贅述說明了。
Python
面試實際可能會遇到的問題
「時間/空間複雜度？」
(O(N)/O(1))
相似及延伸
這題理論上也可以用遞迴的方法解，有興趣的讀者可以嘗試看看。
Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~
感謝大家對這系列文章的支持！這邊跟大家自我工商一下：
筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VEQZV7E**