83. Remove Duplicates From Sorted List - Explanation

1. Recursion

Intuition

We solve the problem from the end of the list backward. First, we recursively remove duplicates from the rest of the list, then check if the current node duplicates its (now cleaned) next node. If so, we skip the current node by returning its next. This naturally handles chains of duplicates.

Algorithm

Base case: if the list is empty or has one node, return it.
Recursively clean the rest of the list starting from head.next.
Update head.next to point to the cleaned sublist.
If the current node's value equals the next node's value, return head.next (skip current).
Otherwise, return head (keep current).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        head.next = self.deleteDuplicates(head.next)
        return head if head.val != head.next.val else head.next

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

2. Iteration - I

Intuition

Since the list is sorted, duplicates are consecutive. At each node, we skip over all following nodes with the same value by adjusting the next pointer. This removes entire chains of duplicates in one pass through the list.

Algorithm

Start with a pointer cur at the head.
While cur is not null, check if the next node has the same value.
If so, skip the next node by setting cur.next = cur.next.next.
Continue skipping until the next node has a different value.
Move cur to the next node and repeat.
Return the head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur:
            while cur.next and cur.next.val == cur.val:
                cur.next = cur.next.next
            cur = cur.next
        return head

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

3. Iteration - II

Intuition

A slightly different structure: instead of a nested loop, we use a single loop with a conditional. If the current and next values match, we skip the next node. If they differ, we advance the pointer. This achieves the same result with cleaner control flow.

Algorithm

Start with a pointer cur at the head.
While both cur and cur.next exist:
- If they have the same value, skip the next node by updating cur.next.
- Otherwise, advance cur to the next node.
Return the head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Advancing the Pointer Incorrectly

When removing a duplicate, you should only update cur.next to skip the duplicate node, but not advance cur itself. If you move cur forward after removing a node, you might skip checking whether the new next node is also a duplicate. Only advance cur when the next node has a different value.

Not Handling Null Pointers

When accessing cur.next.val, you must first verify that cur.next is not null. Forgetting this check leads to null pointer exceptions on the last node or empty lists. Always structure your loop condition as while cur and cur.next or check cur.next != null before accessing its value.