Skip to main content

66. Remove Duplicates from Sorted List II

mediumAsked at Ola

Delete all nodes that have duplicate numbers from a sorted linked list.

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

  • Number of nodes is in [0, 300]
  • -100 <= Node.val <= 100

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]

Approaches

1. Count then rebuild

Count each value into a map, then rebuild a new list with values whose count is 1.

Time
O(n)
Space
O(n)
const m = new Map(); let n = head;
while (n) { m.set(n.val,(m.get(n.val)||0)+1); n = n.next; }
const dummy = {next:null}; let t = dummy;
for (const [v,c] of m) if (c === 1) { t.next = {val:v, next:null}; t = t.next; }
return dummy.next;

Tradeoff:

2. Pointer with skip block

Use a dummy; if prev.next.val == prev.next.next.val, skip every node with that value before relinking.

Time
O(n)
Space
O(1)
function deleteDuplicates(head) {
  const dummy = { next: head };
  let prev = dummy;
  while (prev.next) {
    let curr = prev.next;
    if (curr.next && curr.val === curr.next.val) {
      const val = curr.val;
      while (curr && curr.val === val) curr = curr.next;
      prev.next = curr;
    } else {
      prev = curr;
    }
  }
  return dummy.next;
}

Tradeoff:

Ola-specific tips

Ola checks if you do the skip cleanly without losing prev.next; tie it to trimming repeating duplicate driver heartbeats before a payout reconciliation.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Remove Duplicates from Sorted List II and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →