# Remove Duplicates from Sorted List II

## # Solution

### # Iteration

`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(0)
dummy.next = curr

while curr and curr.next:
if curr.val == curr.next.val:
# loop until `curr` 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
``````
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Or:

``````def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
pred = dummy

while pred.next:
curr = pred.next
# after the loop, `curr` points to the last duplicate
while curr.next and curr.val == curr.next.val:
curr = curr.next
# checks if the inner while loop is entered
if curr is not pred.next:
# eliminate all duplicates
pred.next = curr.next
else:
pred = curr
return dummy.next
``````
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

### # Recursion

Always pass the next non-duplicate node to next recursion.

``````def deleteDuplicates(self, head: ListNode) -> ListNode:
else:
``````
1
2
3
4
5
6
7
8
9

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

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

def rm(self, dup_node: ListNode, dup_val: int) -> ListNode:
if dup_node and dup_node.val == dup_val:
return self.rm(dup_node.next, dup_val)
else:
return dup_node
``````
1
2
3
4
5
6
7
8
9
10
11
12