Remove Duplicates from Sorted List

easy linked list

Problem

Given the head of a sorted linked list, remove all duplicates so that every value appears once. Return the resulting list.

Inputhead = 1 → 1 → 2 → 3 → 3

Output1 → 2 → 3

When cur.next has the same value, skip it by setting cur.next = cur.next.next; otherwise advance cur.

sorted values (comma-separated)

def deleteDuplicates(head):
    cur = head
    while cur and cur.next:
        if cur.val == cur.next.val:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return head

function deleteDuplicates(head) {
  let cur = head;
  while (cur && cur.next) {
    if (cur.val === cur.next.val) cur.next = cur.next.next;
    else cur = cur.next;
  }
  return head;
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) cur.next = cur.next.next;
            else cur = cur.next;
        }
        return head;
    }
}

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur = head;
        while (cur && cur->next) {
            if (cur->val == cur->next->val) cur->next = cur->next->next;
            else cur = cur->next;
        }
        return head;
    }
};

Explanation

Here we keep one copy of each value and drop only the extra duplicates. Since the list is sorted, equal values are always neighbours, so we just compare each node with the one right after it.

A single cur pointer walks the list. If cur.val equals cur.next.val, they are duplicates, so we skip the next node with cur.next = cur.next.next and stay put (in case there are several in a row). If they differ, we advance cur.

Staying put after a deletion is the key detail: it lets us remove a long run of the same value one link at a time without missing any.

Example: 1 → 1 → 2 → 3 → 3. At the first 1 we drop the second 1. Then 1≠2 so move on; 2≠3 move on; at 3 we drop the second 3. Result: 1 → 2 → 3.

One pass, constant extra memory — we only re-point links and never allocate new nodes.

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