Remove Duplicates from Sorted List II

# Solution

# Iteration

We need 2 pointer, `curr`ent and `pred`ecessor. `curr` traverses the linked list while `pred` removes duplicates.

Loop invariant: every node before `pred` does not contain any duplicate.

``````  def deleteDuplicates(self, head: ListNode) -> ListNode:
pred = dummy = ListNode(-1)
dummy.next = curr

while curr and curr.next:
if curr.val == curr.next.val:
# loop until cur point to the last duplicate
while curr and curr.next and curr.val == curr.next.val:
curr = curr.next
pred.next = curr.next
else:
pred = curr
curr = curr.next
return dummy.next
``````

Or create `curr` as `pred.next` in each iteration of while loop. The line `if curr is not pred.next` checks if the inner while loop is entered. After the inner while loop, `curr` points to the last duplicate, so set `pred.next` to `curr.next` eliminates all duplicates.

``````def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode(-1)
pred = dummy
while pred.next:
curr = pred.next
while curr.next and curr.val == curr.next.val:
curr = curr.next
if curr is not pred.next:
pred.next = curr.next
else:
pred = curr
return dummy.next
``````

# Recursion

Always pass the next non duplicate node to next recursion.

``````def deleteDuplicates(self, head: ListNode) -> ListNode:
else:
``````

Or have two recursions. In `rm` remove all duplicate nodes and return the non duplicate one.

``````def deleteDuplicates(self, head: ListNode) -> ListNode: