LeetCode 83: Remove Duplicates from Sorted List Solution in Python Explained

Problem Statement

In LeetCode 83, you’re given the head of a sorted linked list, and your task is to remove all duplicate values, keeping only the first occurrence of each number. Unlike LeetCode 82: Remove Duplicates from Sorted List II, which wipes out all instances of duplicates, here we preserve one node per value. The list stays sorted.

Constraints

• Number of nodes: 0 <= n <= 300
• Node values: -100 <= Node.val <= 100
• The list is sorted in ascending order.

Example

Let’s look at some test cases:

Copy codeInput: head = [1,1,2]
Output: [1,2]
Explanation: Keep the first 1, remove the second 1, keep 2.

Copy codeInput: head = [1,1,2,3,3]
Output: [1,2,3]
Explanation: Keep one of each value: 1, 2, and 3.

Copy codeInput: head = [1,2,3]
Output: [1,2,3]
Explanation: No duplicates, so no changes.

These examples highlight the goal: trim duplicates, not eliminate them entirely.

Understanding the Problem

How do you solve LeetCode 83: Remove Duplicates from Sorted List in Python? Take head = [1,1,2,3,3]. Since it’s sorted, duplicates are consecutive—two 1s, then 2, then two 3s—so we keep the first of each, resulting in [1,2,3]. This isn’t a search problem like LeetCode 1: Two Sum; it’s about refining the list. We’ll use: 1. Iterative: O(n) time, O(1) space—our top choice. 2. Recursive: O(n) time, O(n) space—a sleek option.

Let’s dive into the primary solution with a detailed breakdown.

Solution 1: Iterative Approach (Primary)

Explanation

Since the list is sorted, we can traverse it with a single pointer, comparing each node to the next. If they’re duplicates, we skip the next node by updating the current node’s next pointer; if not, we move forward. No dummy node is needed here, unlike LeetCode 82, because we’re not removing all duplicates—just extras.

For head = [1,1,2,3,3]:

• 1 vs. 1: Skip second 1.
• 1 vs. 2: Keep 2.
• 2 vs. 3: Keep 3.
• 3 vs. 3: Skip second 3.

Result: [1,2,3].

Step-by-Step Example

Assume a ListNode class: class ListNode: def __init__(self, val=0, next=None): self.val = val; self.next = next.

Example 1: head = [1,1,2]

Goal: Return [1,2].

• Start: curr = head (1).
• Step 1: curr.val = 1, curr.next.val = 1, duplicates.
• curr.next = curr.next.next → 1.next = 2 (skip second 1).
• Step 2: curr = 1, curr.next.val = 2, no duplicates.
• curr = curr.next → curr = 2.
• Step 3: curr = 2, curr.next = None, stop.
• Finish: head = [1,2], return it.

Example 2: head = [1,1,2,3,3]

Goal: Return [1,2,3].

• Start: curr = 1.
• Step 1: curr.val = 1, curr.next.val = 1, duplicates.
• 1.next = 2 (skip second 1).
• Step 2: curr = 1, curr.next.val = 2, no duplicates.
• curr = 2.
• Step 3: curr.val = 2, curr.next.val = 3, no duplicates.
• curr = 3.
• Step 4: curr.val = 3, curr.next.val = 3, duplicates.
• 3.next = None (skip second 3).
• Step 5: curr = 3, curr.next = None, stop.
• Finish: head = [1,2,3], return it.

Example 3: head = [1,2,3]

Goal: Return [1,2,3].

• Start: curr = 1.
• Step 1: curr.val = 1, curr.next.val = 2, no duplicates.
• curr = 2.
• Step 2: curr.val = 2, curr.next.val = 3, no duplicates.
• curr = 3.
• Step 3: curr = 3, curr.next = None, stop.
• Finish: head = [1,2,3], return it.

How the Code Works (Iterative) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteDuplicates(head: ListNode) -> ListNode:
    # Line 1: Check if the list is empty or has one node
    if not head or not head.next:
        # If head is None (empty) or head.next is None (single node), no duplicates exist
        # Return the list unchanged (None or single node)
        return head

    # Line 2: Initialize curr pointer to the head
    curr = head
    # curr starts at the first node (e.g., 1 in [1,1,2])
    # We’ll use this to traverse and modify the list

    # Line 3: Loop while curr and curr.next exist
    while curr and curr.next:
        # Condition ensures we can compare curr.val with curr.next.val
        # Stops if curr is None (shouldn’t happen here) or curr.next is None (end of list)

        # Line 4: Compare current node’s value with the next node’s value
        if curr.val == curr.next.val:
            # If true, we’ve found duplicates (e.g., 1 == 1 in [1,1,2])
            # We need to skip the duplicate node

            # Line 5: Skip the duplicate by updating curr.next
            curr.next = curr.next.next
            # Links curr to the node after the duplicate
            # e.g., for [1,1,2], 1.next changes from second 1 to 2
            # The second 1 is effectively removed from the list
            # Note: We don’t move curr here, we check the new next node in the next iteration
        else:
            # If curr.val != curr.next.val, no duplicate (e.g., 1 then 2)

            # Line 6: Move curr to the next node
            curr = curr.next
            # Advances curr to the next unique value (e.g., from 1 to 2)
            # Prepares to check the next pair

    # Line 7: Return the modified list
    return head
    # head now points to the list with duplicates removed (e.g., [1,2])
    # No dummy node, so we return head directly

This detailed explanation shows exactly how each line transforms the list, making it accessible for beginners.

Alternative: Recursive Approach

Explanation

Recursion processes the list by checking each node against the next. If duplicates exist, skip the next node; otherwise, recurse on the rest and link back.

For [1,1,2]:

• 1 vs. 1: Skip second 1, recurse on [1,2].
• 1 vs. 2: Keep 1, recurse on [2].
• 2 vs. None: Return 2.

Result: [1,2].

Step-by-Step Example (Alternative)

For head = [1,1,2,3,3]:

• Call 1: head = 1, head.next.val = 1, duplicates.
• 1.next = recurse([1,2,3,3]).
• Call 2: head = 1, head.next.val = 2, no duplicates.
• 1.next = recurse([2,3,3]).
• Call 3: head = 2, head.next.val = 3, no duplicates.
• 2.next = recurse([3,3]).
• Call 4: head = 3, head.next.val = 3, duplicates.
• 3.next = recurse([3]).
• Call 5: head = 3, head.next = None, return 3.
• Unwind: Return [1,2,3].

How the Code Works (Recursive)

Copy codedef deleteDuplicatesRecursive(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    if head.val == head.next.val:
        head.next = deleteDuplicatesRecursive(head.next)
        return head.next
    else:
        head.next = deleteDuplicatesRecursive(head.next)
        return head

Complexity

• Iterative:
• Time: O(n) – single pass.
• Space: O(1) – just a pointer.
• Recursive:
• Time: O(n) – each node once.
• Space: O(n) – recursion stack.

Efficiency Notes

Iterative is optimal with O(1) space and simplicity, while recursive is elegant but stack-heavy—great for practicing recursion, like in LeetCode 206: Reverse Linked List.

Key Insights

• Sorted Advantage: Duplicates are consecutive.
• Single Pass: No need for extra nodes.
• Keep First: Only skip extras.

Additional Example

For head = [1,1,1,2]:

• Goal: [1,2].
• Iterative: Skip two 1s, keep 2 → [1,2].

Edge Cases

• Empty List: [] → [].
• Single Node: [1] → [1].
• No Duplicates: [1,2,3] → [1,2,3].

Both solutions handle these effortlessly.

Final Thoughts

LeetCode 83: Remove Duplicates from Sorted List in Python is a perfect intro to linked list manipulation. The Iterative solution is straightforward and efficient, while Recursive adds a stylish twist. Want more? Try LeetCode 82 for a tougher duplicate challenge or LeetCode 80: Remove Duplicates from Sorted Array II for arrays. Ready to practice? Solve LeetCode 83 on LeetCode with [1,1,2,3,3] and aim for [1,2,3]—test your skills now!