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
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
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.
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
@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
@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)
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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.