Remove Duplicates from Sorted List II

Medium
2005.

Remove Duplicates from Sorted List II

Remove Duplicates from Sorted List II is a medium coding problem on two pointers, asked in Amazon, Microsoft, Meta and Bloomberg interviews.

You are given the head of a singly linked list sorted in non-decreasing order. Delete every node whose value appears more than once in the list, keeping only the values that occur exactly once, and return the head of the resulting list (still sorted).

Example 1

Input
head = [1,2,3,3,4,4,5]
Output
[1,2,5]
Explanation
3 and 4 each appear twice, so all their nodes go.

Example 2

Input
head = [1,1,1,2,3]
Output
[2,3]
Explanation
The run of 1s at the head is removed completely.

Example 3

Input
head = [7,7]
Output
[]

Constraints

  • The number of nodes in the list is in the range [0, 300]
  • -100 <= Node.val <= 100
  • The list is sorted in non-decreasing order
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Duplicates from Sorted List II — Problem & Solution

Remove Duplicates from Sorted List II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Remove Duplicates from Sorted List II is a medium coding problem on two pointers, asked in Amazon, Microsoft, Meta and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Two Pointers
  • Asked at: Amazon, Microsoft, Meta, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the head of a singly linked list sorted in non-decreasing order. Delete every node whose value appears more than once in the list, keeping only the values that occur exactly once, and return the head of the resulting list (still sorted).

Example 1

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Explanation: 3 and 4 each appear twice, so all their nodes go.

Example 2

Input: head = [1,1,1,2,3]
Output: [2,3]
Explanation: The run of 1s at the head is removed completely.

Example 3

Input: head = [7,7]
Output: []

Constraints

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

Hints for Remove Duplicates from Sorted List II

  1. Hint 1

    In a sorted list, all copies of a value form one consecutive run. A value survives exactly when its run has length 1.

  2. Hint 2

    Keep prev, the last node known to survive, and look at the run that starts at prev.next.

  3. Hint 3

    If the run is longer than one node, skip all of it with prev.next = <first node after the run>; otherwise advance prev. A dummy node handles a duplicated head.

How to solve Remove Duplicates from Sorted List II

Examine the list run by run. A run of equal values of length one is kept; a longer run is cut out entirely by linking the last kept node past it.

Approach

  1. Create a dummy node before head and set prev = dummy.
  2. While prev.next exists, let cur = prev.next.
  3. If cur.next exists and has the same value, advance cur to the last node of the run and set prev.next = cur.next (the whole run disappears; prev stays).
  4. Otherwise the value is unique: prev = prev.next.
  5. Return dummy.next.

Why it works

prev only ever moves onto a node whose run has length one, and every longer run is unlinked as a whole before prev looks past it. So exactly the unique values remain, in their original sorted order.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Unlike LC 83, the first copy is not kept — the whole run goes.
  • After removing a run, do not advance prev: the next run may also be duplicated.
  • The head itself may be part of a duplicated run; the dummy node covers that.

Reference solution

Python

from typing import Optional

def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        cur = prev.next
        if cur.next and cur.next.val == cur.val:
            while cur.next and cur.next.val == cur.val:
                cur = cur.next
            prev.next = cur.next
        else:
            prev = cur
    return dummy.next

Java

public static ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode(0, head), prev = dummy;
    while (prev.next != null) {
        ListNode cur = prev.next;
        if (cur.next != null && cur.next.val == cur.val) {
            while (cur.next != null && cur.next.val == cur.val) cur = cur.next;
            prev.next = cur.next;
        } else {
            prev = cur;
        }
    }
    return dummy.next;
}

C++

ListNode* deleteDuplicates(ListNode* head) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    while (prev->next) {
        ListNode* cur = prev->next;
        if (cur->next && cur->next->val == cur->val) {
            while (cur->next && cur->next->val == cur->val) cur = cur->next;
            prev->next = cur->next;
        } else {
            prev = cur;
        }
    }
    return dummy.next;
}

JavaScript

var deleteDuplicates = function(head) {
    var dummy = new ListNode(0, head), prev = dummy;
    while (prev.next !== null) {
        var cur = prev.next;
        if (cur.next !== null && cur.next.val === cur.val) {
            while (cur.next !== null && cur.next.val === cur.val) cur = cur.next;
            prev.next = cur.next;
        } else {
            prev = cur;
        }
    }
    return dummy.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 165 two pointers problems · the whole catalogue

Learn the technique: Two Pointers Technique