Remove Duplicates from Sorted List

Definition for Singly-Linked List

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

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.

Don't need dummy node b/c would always keep the 1st node.

Complexity

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

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None:
        return head
    curr = head
    while curr.next:
        if curr.val == curr.next.val: # next node is a duplicate
            curr.next = curr.next.next
        else: # not duplicate
            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