Remove Duplicates from Sorted List — Editorial

Opening the reading…

Intuitionwhy one pass is enough

A sorted list places equal values next to one another, so duplicates form consecutive runs such as 1, 1, 1 or 3, 3. For each run, the first node is the one you keep. Every later node has the same value as the node immediately before it, so it can be removed without searching elsewhere in the list.

Keep a pointer named current at the last node that remains in the answer. Compare current with current->next. If their values match, bypass current->next and leave current where it is, because another duplicate may still follow. If they differ, current is already the last kept node for its value, so advance it.

Unlinking a duplicate while keeping current on the same value

Approach

Return nullptr immediately when head is null, because an empty list has no node from which traversal can begin.

Set current to head and continue while both current and current->next exist, because every comparison needs a valid node and its successor.

When current->val equals current->next->val, save the duplicate node, redirect current->next to current->next->next, and delete the removed node; staying on current is necessary to remove a run of three or more equal values.

When the two values differ, advance current to current->next, because the current node is now the final kept node for its value and cannot remove its successor.

Repeat until current has no next node, because the final node has nothing to compare against and the list is then fully processed.

Return head rather than creating a new list, because the original first node is always kept and all changes happen by editing next pointers.

Complexityeach node is examined a constant number of times

MEASURE	BOUND	WHY
Time	O(n)	current moves forward at most n - 1 times, and each duplicate is unlinked once. A node is never revisited after current passes it, so the total number of comparisons and pointer changes is linear.
Space	O(1) extra	Only current and one temporary pointer are used, regardless of the list shape. The returned list is required output and is excluded from the extra-space bound; the input is already a single chain, so there is no deeper worst case to add.

Here n means the number of nodes in the input list.

Annotated solutionC++ · iterative in-place pointer traversal

CPPWalk the sorted list once and unlink each duplicate node in place.

#include <cstddef>

using namespace std;

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return nullptr;

        ListNode* current = head;
        while (current && current->next) {
            if (current->val == current->next->val) {
                ListNode* duplicate = current->next;
                current->next = current->next->next;
                delete duplicate;
            } else {
                current = current->next;
            }
        }

        return head;
    }
};

The placement of current = current->next is the central detail. It belongs only in the unequal branch. After removing one duplicate, current may still be followed by another equal node, so advancing immediately would leave part of a duplicate run in the list. The temporary pointer is deleted after the link is redirected, which preserves the suffix before releasing the removed node.