0083. Remove Duplicates from Sorted List - chasel2361/leetcode GitHub Wiki

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

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

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

這個題目延續了之前寫過的 Merge Two Sorted Lists ，仍然是處理串列的問題，只是把問題從結合兩個串列改成移除重複值，所以處理概念相當類似

[1] res 指向 head
[2] 檢查 head 以及 head.next 是否存在
[3] 若 head.val 與 head.next.val 相同，將 head.next 指向 head.next.next (跳過 head.next )
[4] 若否則不須跳過

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        res = head  # [1]
        while head and head.next:  # [2]
            if head.val == head.next.val:  # [3]
                head.next = head.next.next
            else:  # [4]
                head = head.next
        return res

這樣寫的時間複雜度是 O(N) ，空間複雜度是 O(N)

---

看了一下 Medium 大大的寫法，他是把重複的值先存到一個 tmp 裡，當重複結束之後再把 res 指到 tmp

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        res = head
        while res:
            tmp = res.next
            while tmp and res.val == tmp.val:
                tmp = tmp.next
            res.next = tmp
            res = tmp
        return head

雖然這樣寫感覺蠻有道理的，而且時間複雜度跟空間複雜度也相同，可是 tmp 重複時要指向 tmp.next，出了迴圈又要再跟 res 接一次，這樣感覺有點疊床架屋囧

Code Link