###### tags: `Leetcode` `medium` `list` `python`

# 82. Remove Duplicates from Sorted List II

## [題目連結:]https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

## 題目:
Given the ```head``` of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list **sorted** as well.


#### [圖片來源:] https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

## 解題想法:
* 題目要求，若出現重複的node，則一律全部刪除
* 設兩個pointer:
* pre:紀錄先前位置
* cur:探索當前位置
* while判斷cur.val==cur.next.val判斷是否遇到重複
* 額外設個flag=True:
* 用已紀錄是否當前遭遇重複node
* 若遇重複node，則改為False
* 最後判斷flag:
* 若為True:
* pre正常往前
* else:
* pre.next=cur.next (跳過中間重複的)
* pre不用移動
* cur不影響，依舊正常往前

* 示意圖:

## Python:

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next = ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head = self
        tmp = []
        while head:
            tmp.append(head.val)
            head=head.next
        print(tmp)
        
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy=ListNode(0)
        dummy.next=head
        pre=dummy
        cur=head
        flag=True
        while cur:
            #若重複的cur就一直移動到重覆的最後一個位置
            while cur.next and cur.val==cur.next.val:
                cur=cur.next
                flag=False
            if flag:
                #表示安全沒遇到重複狀況
                pre=pre.next
            else:
                pre.next=cur.next
                flag=True
            cur=cur.next
        return dummy.next

head=ListNode(1)
head.insert(2)
head.insert(3)
head.insert(3)
head.insert(4)
head.insert(4)
head.insert(5)

head.printList()
result = Solution()
ans = result.deleteDuplicates(head)
ans.printList()