Remove Duplicates from Sorted List II

medium linked list two pointers

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.

Use a dummy head so that even the first run can be unlinked uniformly. Walk a prev pointer along the kept prefix; for each node compare it with its neighbour. If it starts a duplicate run, advance through the run and splice prev.next past the whole run; otherwise advance prev.

Input1 → 2 → 3 → 3 → 4 → 4 → 5

Output1 → 2 → 5

sorted list (comma-separated)

def delete_duplicates(head):
    dummy = ListNode(0, head)
    prev = dummy
    cur = head
    while cur:
        if cur.next and cur.val == cur.next.val:
            v = cur.val
            while cur and cur.val == v: cur = cur.next
            prev.next = cur
        else:
            prev = cur; cur = cur.next
    return dummy.next

function deleteDuplicates(head) {
  const dummy = { val: 0, next: head };
  let prev = dummy, cur = head;
  while (cur) {
    if (cur.next && cur.val === cur.next.val) {
      const v = cur.val;
      while (cur && cur.val === v) cur = cur.next;
      prev.next = cur;
    } else {
      prev = cur; cur = cur.next;
    }
  }
  return dummy.next;
}

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

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

Explanation

This version is stricter: if a value appears more than once, every copy of it must go, not just the extras. Because the list is sorted, all equal values sit next to each other, so a duplicate run is easy to spot and skip past entirely.

We use a dummy head so even a duplicate run at the very front can be removed cleanly. A prev pointer trails along the part of the list we are keeping, and cur scans ahead. If cur and cur.next share a value, we have found a duplicate run.

When that happens, we remember the value v and walk cur forward until it leaves the run, then set prev.next = cur to splice the whole run out at once. If cur is unique, we simply move prev forward to it.

Example: 1 → 2 → 3 → 3 → 4 → 4 → 5. The 3s form a run (both removed), the 4s form a run (both removed), leaving 1 → 2 → 5.

It is a single pass with constant extra space, since we only relink pointers and never copy nodes.

Time: O(n) Space: O(1)