0083. Remove Duplicates from Sorted List (Easy)

Question

Given a sorted linked list, delete all duplicates such that each element appears only once.

Example 1

1
2

Input: 1->1->2
Output: 1->2

Example 2

1
2

Input: 1->1->2->3->3
Output: 1->2->3

分析/解題

題目給定一個已排序好的linked list，要求將所有重複的node皆刪除，
使得每個元素均只出現一次。

這題也算是比較簡單的linked list類型，只要確定連接正確的話並不難解。
由於已經排序過的原因，所有會重複的元素值均會相鄰，那麼我們所要做的就是遇到重複時總共只保留一個就好了 。
保留哪一個呢？當然是保留第一個囉！

我們可以先宣告一個ListNode，命名為ite用來做為iterator(迭代器)，
每次取得ite的下一個node(命名為tmp)做為暫存。
接下來開始一路往下尋找，如果ite和tmp前後值相等時，就讓tmp開始往下一直走到底部(表示後面值都一樣) 或者找到下一個不同的值。 對於前者的狀況 而言，表示結束，tmp會指到null(或None)，
只要將ite.next指向到tmp 即可。

對於後者的狀況 ，這時候tmp的位置就在下一個相異值的點 。
像是1->2->2->2->3->4這樣子，從ite在碰到第一個2以後，
tmp會一路找到3的位置，所以我們只要將ite.next指向到tmp ，
即可將第一個2接到3的位置，從而中間的部分就等於被我們刪去了。

討論完兩者狀況後，我們會發現無論是哪一種，
結果都會是將ite.next指向到tmp，
最後要記得ite本身要遞移到下一個開始找的位置，
所以我們還需要將tmp的位置交給ite。

Java

以Python的部分來說，還記得判斷式可以直接適用於if的話，
就可以寫得看起來簡潔一些。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(1))

其它應該沒什麼好問的，至少我沒想到XD
這篇主要是協助讀者再熟悉一下這些連接/斷開的操作。

從LeetCode學演算法，我們下次見囉，掰~