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

  • 0
    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
    # # do not forget corner cases
            if head == None:
                return None
            p =
            a = [head.val]
            # record all duplicate numbers
            duplicateNumber = []
            while p != None:
                if p.val == a[-1]:
                    while p != None and p.val == a[-1]:
                        p =
                    if p == None: break
                    else: a.append(p.val)
                else:  a.append(p.val)
                p =
            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]:
                # or look at next duplicate number in duplicateNumber
                    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.
     if head == None:
                return None
            if == None:
                return head
            guard = ListNode("guard")
            sentinel = guard
            p = head
            while p != None and != None:
                if p.val ==
                    while != None and p.val ==
                        p =
                    if sentinel.val == "guard":
                        head =
                    sentinel = p
                p =
            return head

Log in to reply

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