MediumLinked ListTwo PointersRecursion

Remove Duplicates from Sorted List II

1 approach, code in every language

You are given the head of a sorted singly linked list. Remove every node whose value appears more than once, keeping only the values that are unique across the entire list.

Unlike the simpler variant that keeps one copy of each value, here a value that repeats is deleted completely. The remaining nodes must stay in their original sorted order. Return the head of the resulting list.

Example 1

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

Output: [1,2,5]

The values 3 and 4 each occur twice, so all of their nodes are removed, leaving only 1, 2, and 5.

Example 2

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

Output: [2,3]

The value 1 repeats three times and is dropped entirely, while 2 and 3 appear once and survive.

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.

Recursion

At each head, either skip an entire run of duplicates and recurse on the first different node, or keep the head and recurse on the rest.

Loading animation…

Intuition

Because the list is sorted, all copies of a value sit next to each other, which makes duplicates easy to detect by comparing a node with its immediate successor. If the head shares its value with the next node, the head is part of a duplicated run, so we advance past every node carrying that value and recurse from the first node with a new value; none of the skipped nodes belong in the answer. If the head's value differs from the next node's value, the head is unique so far, so we keep it and simply recurse on the remainder, wiring the returned list into head.next. The base case of an empty or single-node list needs no work.

Algorithm walkthrough

1Base case: if head or head.next is null, return head since a run of duplicates needs at least two nodes.
2If head.val equals head.next.val, record that value and walk head forward while it keeps matching, discarding the whole duplicate block.
3Return the recursive result on the first node whose value differs, since the entire matched block is excluded from the answer.
4Otherwise head is distinct: set head.next to the recursive result on head.next to clean the rest of the list.
5Return head, now guaranteed to be a unique value followed by an already-deduplicated tail.

Implementation

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

Time

O(n)

Space

O(n)

Every node is examined once, and the recursion depth is O(n) in the worst case of no duplicates.

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.

Unique Scan Trim is our own problem on the technique behind Remove Duplicates from Sorted List II: 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