python o(1) o(n) three pointers solutions


  • 0

    Straight forward using three pointers

    • using prepre to record the start point
    • using pre to record the start point of the same value and cur indicate the end index of the same value
        def deleteDuplicates(self, head):
            if not head or not head.next:
                return head
                
            newhead=ListNode(-2<<31-1)
            # the fisrt pointer
            prepre=newhead
            newhead.next=head
            # the second 
            pre=head
            # the third
            cur=head.next
            
            while cur:
                if pre.val==cur.val:
                    # find the cur that not equal to pre
                    while cur and pre.val==cur.val:
                        cur=cur.next
                    # if reach the end,beak
                    if not cur:
                        prepre.next=None
                        break
                    # else move on pre cur and prepre
                    else:
                        # record the next possible value
                        p=cur.next
                        # delete all the value before
                        prepre.next=cur
                        # update the the second and third point
                        pre=cur
                        cur=p
                else:
                    prepre=pre
                    pre=cur
                    cur=cur.next
                    
            return newhead.next
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.