leetcode-LL

82. Remove Duplicates from Sorted List II.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    """
    不囉唆, remove nodes we need to initialize two pointers prev and cur  
    d -> 1 ->1->1->1
    prev cur
                  cur
    
    
    d -> 1 ->2->3->4
    prev cur
       prev cur
           prev cur
               prev cur
                   prev cur
                   
    d = ListNode(-1)
    d.next = head
    prev = d
    cur = d.next
    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 # remove all the duplicates from linked list
            cur = cur.next
        else:
            cur = cur.next
            prev = prev.next
    return d.next
    Ref:
        https://www.youtube.com/watch?v=82A7Je0dHFA&ab_channel=TimothyHChang
    """
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        """
        prev and cur two pointers
        """
        if not head:
            return head
        
        d = ListNode(-1)
        d.next = head
        prev = d
        cur = d.next
        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 = cur.next
            else:
                prev = prev.next
                cur = cur.next
        return d.next
    
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        """
        Counter
        """
        cur = head
        nums = []
        while cur:
            nums.append(cur.val)
            cur = cur.next
        counter = collections.Counter(nums) 
        # traverse the given ll
        d = ListNode(-1)
        d.next = head
        cur = d.next
        # gnerate output ll
        output = ListNode(-1)
        m = output
        while cur:
            if counter[cur.val] > 1:
                cur = cur.next
                continue
            m.next = ListNode(cur.val)
            m = m.next
            cur = cur.next
        return output.next