Python in-place solution with dummy head node.


  • 16
    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

  • 0
    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!


  • 0

    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


Log in to reply
 

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