Remove All Duplicates From a Sorted List

medium linked list two pointers

Problem

From a sorted linked list, delete every node whose value appears more than once — keep only values that appear exactly once.

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;
}

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