EasyLinked List

Remove Duplicates from Sorted List

1 approach, code in every language

You are given the head of a linked list that is already sorted in non-decreasing order. Remove every duplicate value so that each distinct number appears only once.

The list must remain sorted after the removals. Return the head of the modified list.

Example 1

Input: head = [1,1,2]

Output: [1,2]

The second occurrence of 1 is unlinked, leaving one node per distinct value.

Example 2

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

Output: [1,2,3]

Both runs of duplicates (the pair of 1s and the pair of 3s) collapse to a single node each.

Constraints

The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in non-decreasing order.

Single Pointer Skip

Sweep once with a single pointer, unlinking any next node that repeats the current value.

Loading animation…

Intuition

Since the list is sorted, every group of equal values sits together as a contiguous run. That means detecting a duplicate is purely local: if a node has the same value as the node directly after it, the successor is redundant. We keep one pointer at the current node and peek at its next node. When they match, we bypass the successor by pointing current.next past it; otherwise the current node is the last of its value group and we move forward. We only advance the pointer when we did not delete, so a run of three or more equal values collapses correctly in a single pass.

Algorithm walkthrough

1Start with a pointer curr at the head of the list.
2Loop while curr is not null and curr.next is not null.
3If curr.val equals curr.next.val, splice out the duplicate by setting curr.next to curr.next.next.
4Otherwise, the values differ, so advance curr to curr.next.
5Do not advance curr after a deletion, so consecutive duplicates are all removed.
6Return the original head, which still points at the first node.

Implementation

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        current = head
        while current and current.next:
            if current.val == current.next.val:
                current.next = current.next.next
            else:
                current = current.next
        return head

Time

O(n)

Space

O(1)

Each of the n nodes is examined once and duplicates are unlinked in place, so no auxiliary structures are required.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Trim Repeat Holds is our own problem on the technique behind Remove Duplicates from Sorted List: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free