Remove Duplicates from Sorted List

https://leetcode.com/problems/remove-duplicates-from-sorted-list

# Solution

# Iteration

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

Complexity:

  • time: O(n)O(n)
  • space: O(1)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

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
Last Updated: 7/19/2020, 3:45:14 PM