Remove Duplicates from Sorted List

Solution

Let $n$ be the length of the linked list.

Iteration

As the input list is sorted, we can compare curr.val w/ curr.next.val. If same, skip the duplicate; otherwise, go to curr.next.

Complexity

time: $O(n)$
space: $O(1)$

def deleteDuplicates(self, head: ListNode) -> ListNode:
    curr = head
    while curr and curr.next:
        if curr.val == curr.next.val:
            curr.next = curr.next.next
        else:
            curr = curr.next
    return head

Recursion

The recursive deleteDuplicates does not update curr until curr.next is the last of duplicates.

Complexity

time: $O(n)$
space: $O(n)$ (due to implicit stack space)

def deleteDuplicates(self, head: ListNode) -> ListNode:
    curr = head
    if not curr or not curr.next: return head
    if curr.val == curr.next.val:
        curr.next = curr.next.next
        self.deleteDuplicates(curr)
    else:
        self.deleteDuplicates(curr.next)
    return head