Python solutions: A simple Space O(N) version and an in place, space O(1) solution


  • 0
    X
    1. space O(N)
      idea: the idea is really simple: we loop through the list and record in an array which is duplicate and which is not. Then we create a new linked list (here I just use array) to paste all non-duplicate elements in to it
      code:
    # # do not forget corner cases
            if head == None:
                return None
            p = head.next
            a = [head.val]
            # record all duplicate numbers
            duplicateNumber = []
            while p != None:
                if p.val == a[-1]:
                    duplicateNumber.append(p.val)
                    while p != None and p.val == a[-1]:
                        p = p.next
                    if p == None: break
                    else: a.append(p.val)
                else:  a.append(p.val)
                p = p.next
            
            i, res = 0, []
            for j in range(len(a)):
                # if all duplicate numbers has been considered
                if i >= len(duplicateNumber):
                    return res + a[j:]
                # if a[j] is not duplicate number, paste it to a
                elif a[j] != duplicateNumber[i]:
                    res.append(a[j])
                # or look at next duplicate number in duplicateNumber
                else:
                    i += 1
            return res
    
    1. An in-place space O(1) version
      idea: We set a sentinel. This sentinel should point to the element before the first duplicated elements so far. When p get to the end of the duplicated element sequence, set sentinel's next to p's next so that we dump all the duplicated elements.
      I also set a guard node to deal with corner cases when head points to a duplicated element.
      code:
     if head == None:
                return None
            if head.next == None:
                return head
            guard = ListNode("guard")
            sentinel = guard
            p = head
            while p != None and p.next != None:
                if p.val == p.next.val:
                    while p.next != None and p.val == p.next.val:
                        p = p.next
                    if sentinel.val == "guard":
                        head = p.next
                    else:
                        sentinel.next = p.next
                else:
                    sentinel = p
                p = p.next
            return head
    

Log in to reply
 

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