題目出處
83. Remove Duplicates from Sorted List
難度
easy
題目分類
Linked List
個人範例程式碼
記得上述所說的，我們需要先宣告 None 作為結尾
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur and cur.next: # [1,1,1]
if cur.val == cur.next.val:
cur.next = cur.next.next # pass one # need check many times
else:
cur = cur.next # duplicat 1 in index 0 moved !!!
return head
Time Complexity
O(n)
Space Complexity
O(1)
算法說明
利用先前提到的 remove 方法，
操作「cur.next cur.next.next」的時機。
corner case 特殊情況處理
一同整理在下方「邊際情況處理」
Boundary conditions/ Edge conditions 邊際情況處理
這題很可惜沒有一次就寫對，我只有思考到以下前三種情況：
- - []
- [1]
- [1,1]
- [1,1,1]
至於為什麼第四種情況會出問題?
當時我的 code 長這樣
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur and cur.next: # [1,1,1]
if cur.val == cur.next.val:
cur.next = cur.next.next # pass one # need check many times
cur = cur.next # duplicat 1 in index 0 moved !!!
return head
讀者可以先閱讀一下，看看能不能自己發現問題點在哪? (但我註解好像已經寫了 Orz)
總之是以上操作會有一個問題是，每一次必做 cur = cur.next，
當有類似 [1,1,1] 的 case 時，判斷完前兩個相同，第一個 1 就當作沒問題往下走了，
下一步會是第三個位置，但第一三位置的重複沒有判斷到 !!!