Remove Duplicates from Sorted List: A Clean & Simple Visual Guide

The Core Problem

Imagine you are looking at a line of numbered boxcars on a train track. Your job is to make sure every boxcar has a unique number. Normally, finding duplicates would require checking the entire train multiple times.

However, there is a massive advantage given to us in this problem: the linked list is already sorted.

Because the list is sorted in ascending order, any duplicate values are guaranteed to be sitting right next to each other.

• Example 1: Input: head = [1, 1, 2] -> Output: [1, 2]
• Example 2: Input: head = [1, 1, 2, 3, 3] -> Output: [1, 2, 3]

The challenge is to iterate through this list and sever the ties to any redundant nodes, effectively cutting them out of the chain.

Interactive Visualization

Walk through the logic step-by-step using the interactive visualizer below. Watch how the pointer successfully skips over redundant nodes by simply rerouting the arrow.

Single Pointer Traversal

The optimal approach is remarkably straightforward. Because we know duplicates are adjacent, we only need a single pointer (curr) to traverse the list.

Here is the real-world analogy:

1. You stand on the first train car (curr).
2. You look at the car immediately coupled behind it (curr.next).
3. If they have the exact same number: You uncouple the next car and instead throw your coupling hook to the car after that one (curr.next = curr.next.next). You stay exactly where you are to check if the new car you just hooked up is also a duplicate!
4. If they have different numbers: Everything is perfectly fine. You walk forward to the next car (curr = curr.next) and repeat the process.

This process continues until you either run out of cars or the car you are standing on is the last one in the line.

Code Implementations

Here is the production-ready code in three popular languages. Notice how short and elegant the logic is.

TypeScript / JavaScript

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val);
        this.next = (next===undefined ? null : next);
    }
}

function deleteDuplicates(head: ListNode | null): ListNode | null {
    let curr = head;

    while (curr !== null && curr.next !== null) {
        if (curr.val === curr.next.val) {
            // Duplicate found: bypass the next node
            curr.next = curr.next.next;
        } else {
            // Values are distinct: move pointer forward
            curr = curr.next;
        }
    }
    
    return head;
}

Python 3

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]:
        curr = head
        
        while curr and curr.next:
            if curr.val == curr.next.val:
                # Bypass the duplicate node
                curr.next = curr.next.next
            else:
                # Move to the next unique node
                curr = curr.next
                
        return head

Java

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode curr = head;
        
        while (curr != null && curr.next != null) {
            if (curr.val == curr.next.val) {
                // Skip over the duplicate node
                curr.next = curr.next.next;
            } else {
                // Advance the pointer
                curr = curr.next;
            }
        }
        
        return head;
    }
}

Complexity Analysis

• Time Complexity: O(N). We traverse the linked list exactly once. At each step, we either delete a duplicate or move our curr pointer forward. Therefore, the time taken scales linearly directly with the number of nodes (N) in the list.
• Space Complexity: O(1). We are performing this operation in-place. We only allocate memory for a single curr pointer, which means our extra memory usage remains strictly constant regardless of the size of the input list.

Summary & Key Takeaways

1. Rely heavily on the fact that the list is sorted. It transforms an otherwise $O(N^2)$ or Hash Map problem into a simple adjacent comparison problem.
2. When you bypass a node (curr.next = curr.next.next), do not advance your curr pointer immediately. The newly attached node might also be a duplicate of your current node (e.g., [3, 3, 3]).
3. Always check that curr and curr.next are not null before trying to read their .val properties to prevent runtime crashes.

Stay sharp for coding assessments and final exams! Use our free academic tools, including the GPA to Percentage Calculator, to check your academic stats and keep your records in order.