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

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
return None
# 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
guard = ListNode("guard")
sentinel = guard
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":