Skip to main content

82. Remove Duplicates from Sorted List II

medium

Like 83 but stricter — any value that appears more than once is removed entirely, not collapsed to a single occurrence. The dummy-head plus look-ahead pattern: you peek two nodes forward to decide whether to skip a whole run.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

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 ascending order.

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Unlike the easy version, the head itself may need to go — use a dummy node.

Hint 2

Stand at prev = dummy. Peek at prev.next and prev.next.next. If their values match, skip every subsequent node sharing that value, then rewire prev.next to skip the whole run.

Hint 3

Only advance prev when prev.next is a confirmed-unique node. Otherwise prev stays put while you keep skipping.

Solution approach

Reveal approach

Dummy-head with look-ahead skip. Allocate a dummy with dummy.next = head and let prev = dummy. Loop while prev.next is non-null: if prev.next.next exists and prev.next.val == prev.next.next.val, capture dupVal = prev.next.val and run an inner loop that advances prev.next while prev.next and prev.next.val == dupVal — this excises the entire run by reassigning prev.next past every duplicate, including the one that was prev.next itself. Otherwise, advance prev = prev.next. Return dummy.next. The key invariant: prev always points at the last confirmed-unique node, never inside a duplicate run. O(n) time, O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • linked-list
  • dummy-head
  • pointer-rewiring

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Remove Duplicates from Sorted List II and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →