# Leetcode 82. Remove Duplicates from Sorted List II

## 題解

# 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]:
        # Time complexity: O(n)
        # Space complexity: O(1)
        dummy = ListNode(0,head)
        prev = dummy
        cur = head
        while cur:
            if cur.next and cur.val == cur.next.val: # 找到有重複元素
                while cur.next and cur.val == cur.next.val: # 開始跳過重複元素
                    cur = cur.next
                prev.next = cur.next # 這時候已經沒有重複了，但是不能確定下下個元素是否跟下個元素重複，所以這裡先接上，如果下一次進來還是重複的，就會重新接上，因為指針沒有往下走，所以可以一直替換直到一開始 cur.val != cur.next.val ，這時候就可以真正確定元素為不重複元素
            else: # 
                prev = prev.next
            cur = cur.next # 一個一個看
        return dummy.next