Python in-place solution with dummy head node.


  • 19
    C
    def deleteDuplicates(self, head):
        dummy = pre = ListNode(0)
        dummy.next = head
        while head and head.next:
            if head.val == head.next.val:
                while head and head.next and head.val == head.next.val:
                    head = head.next
                head = head.next
                pre.next = head
            else:
                pre = pre.next
                head = head.next
        return dummy.next

  • 1
    B

    This condition could be written as follow:

    while head.next and head.val == head.next.val:

    since pre-loop if head.next is not None, then next loop the head must be not None


  • 0
    S

    Very good and concise solution!


  • -1

    According to [wiki] (https://en.wikipedia.org/wiki/In-place_algorithm), this algorithm is not actually "in-place" since you are generating a new linked list.


  • 0

    I got a different one.

    def deleteDuplicates(self, head):
            if not head: return None
            d = ListNode(0)
            d.next = head
            tmp = d
            while tmp and tmp.next and tmp.next.next:
                if tmp.next.val == tmp.next.next.val:
                    de = tmp.next.next
                    while de.next and de.next.val == tmp.next.val:
                        de = de.next
                    tmp.next = de.next
                if tmp.next and tmp.next.next and tmp.next.val != tmp.next.next.val:
                    tmp = tmp.next
            return d.next
    

  • 0
    S

    @caikehe I'm confused why dummy.next always point to the first non-duplicate node but not proceed with head? With the testcase[1,1,1,2,3,3,4], dummy.next.val stays at 2 throughout the code and head.val is 2,4. What's the purpose of pre? I know the answer is wrong without pre and pre.next but would you explain why is that? Thanks a lot


  • 0
    W

    @sarayamato for instance:

    # dummy and head point to the same object
    dummy = head = ListNode(0)
    head.next = ListNode(1)
    head = head.next
    # return True 
    print(dummy.next == head)
    
    # dummy.next points to head
    dummy = ListNode(0)
    head = ListNode(1)
    head.next = ListNode(2)
    dummy.next = head
    head = head.next
    # return 1
    print(dummy.next.val)

  • 0
    B

    My version with comments

        def deleteDuplicates(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            
            dummy = ListNode(0);  # construct a dummy node
            dummy.next = head 
    
            pre = dummy           # set up pre and cur pointers
            cur = head
            while cur:
                if cur.next and cur.val == cur.next.val:
                    # loop until cur point to the last duplicates
                    while cur and cur.next and cur.val == cur.next.val:
                        cur = cur.next
                    pre.next = cur.next  # propose the next for pre
                                         # this will be verified by next line
                else:
                    pre = pre.next 
                cur = cur.next
            return dummy.next
    

Log in to reply
 

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