1 題目描述

簡單來說，在有序的listNode中，移除鍊錶中重複的元素，只留下沒有重複的元素。

2 解法

首先要注意的是，題目提到的是有序的鍊錶，這樣就可以很簡單的使用pointer解決這個問題。
一開始我的解法很蠢，我自己都不太想放上來了…我用三個指標，這導致我花了30分鐘才寫完，不僅僅很攏長可讀性還不高。後來我看到有人的解答是用雙指針，這樣就簡單多了。大概重新用雙指針思考一次題目，7分鐘就寫完了。

首先我們會需要兩個指針：

  • pre 用來記錄重複的前一個元素，這樣才可以把 pre.next 接到沒有重複的元素上
  • cur 跟 cur.next 這兩個會不斷的比較，如果相鄰的兩個元素val相同
    • pre 保持原地不動
    • (while loop) cur 要一直往下走直到 cur.val 跟 cur.next.val 不相同
  • 如果發現 pre.next 與 cur 不同時，就要重新接到最新的 cur 上

大概是這種感覺

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None:
        return head

    dummy = ListNode(0, head)
    pre = dummy
    cur = pre.next

    while cur:
        if cur.next and cur.val == cur.next.val:
            while cur.next and cur.val == cur.next.val:
                cur = cur.next
        if pre.next != cur:
            pre.next = cur.next
        else:
            pre = cur
        cur = cur.next

    return dummy.next
爛死的三指針做法不要參考

但是你會發現，很多神韻的雙指針也是這樣處理：

  • fast 就像 cur.next
  • slow 就是 cur
  • pre 就是 pre
  • while fast and slow.val == fast.val 就跟 雙指針的 while cur.next and cur.val == cur.next.val 一樣
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None:
        return head

    dummy = ListNode(0, head)
    pre = dummy
    slow = pre.next
    fast = slow.next if slow is not None else None

    while fast:
        if pre.next == slow and slow.val != fast.val:
            pre = slow
            slow = fast
            fast = fast.next if fast is not None else None
            continue
        elif slow.val == fast.val:
            while fast and slow.val == fast.val:
                fast = fast.next
            slow = fast
            fast = fast.next if fast is not None else None
        if pre.next != slow:
            pre.next = slow

    return dummy.next

時間複雜度：O(N)O(N) 雖然while裡面有while，但是每個元素只會被訪問一次
空間複雜度：O(1)O(1) 因為使用了指針，不需要額外的空間

3 總結

這題不難，一看到是有序的，就應該馬上想到使用pointer解決。只是我錯在使用三個指針，導致寫的很複雜，花了30分鐘才完成，後來看到別人的解法，才發現原來可以這樣簡單解決，因此再重新寫一次，6分鐘就寫完了。
這題的重點就是如果只是比較隔壁關係使用1個pointer比較鄰居就好，另一個pointer放previous的訊息，這樣就可以很快解決這個問題。