82.md

82. Remove Duplicates from Sorted Array II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

my thoughts:

1. tricky part is to skip all duplicates. so when a dup is found, we need while till a diff is found or hit the end of the list. if we found a diff, move p2 to the diff; if we hit the end, p2 stay as None. repeat.

my solution:

**********84 ms
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        dummy = ListNode(0)
        dummy.next = head
        p1, p2 = dummy, head
        while p2 and p2.next:
            if p2.val != p2.next.val:
                p1.next = p2
                p1 = p1.next
                p2 = p2.next
            else:
                while p2.next and  p2.val == p2.next.val:
                    p2 = p2.next
                if p2:
                    p2 = p2.next
        p1.next = p2
        return dummy.next

my comments:

from other ppl's solution:

1. run run run, 72ms:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        prev = None
        start = head
        runner = start.next if start else None
        
        while start:
            if runner is None or runner.val != start.val:
                if start.next == runner:
                    prev = start
                    start = runner
                else:
                    if prev:
                        prev.next = runner
                    else:
                        head = runner
                    
                    start = runner
                    
            runner = runner.next if runner else None
            
        return head