[/dsa/leetcode]

83 - Remove Duplicates from Sorted List

Friday, 18 September 2026

<easy> [problem]

The write pointer from 26 moved onto a linked list, where keeping an element means pointing the last kept node at it instead of copying.

{linked list}{two pointers}

Problem

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

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

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

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

Approach

The first node is always kept, so start prev there and curr one ahead. For each curr:

  • equal to prev->val — a duplicate, so skip it by leaving prev alone.
  • different — the first node of a new value. Link it in with prev->next = curr and move prev.

The last line matters. If the list ends on a run of duplicates, prev is still pointing at the first of that run, which is now the tail, but its next still points into the skipped nodes. prev->next = curr writes the nullptr that curr has just reached and cuts them loose.

head = [1,1,2,3,3]
prev=1a curr=1b   1 == 1   dup            -> curr=2
prev=1a curr=2    2 != 1   link, prev=2   -> 1a->2, curr=3a
prev=2  curr=3a   3 != 2   link, prev=3a  -> 2->3a, curr=3b
prev=3a curr=3b   3 == 3   dup            -> curr=null
prev->next = null                            3a->null
[1,2,3]
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* curr = head;
        ListNode* prev = nullptr;
        if (curr == nullptr || curr->next == nullptr)
            return head;
        prev = curr;
        curr = curr->next;
        while (curr != nullptr) {
            if (prev->val != curr->val) {
                prev->next = curr;
                prev = curr;
            }
            curr = curr->next;
        }
        prev->next = curr;
        return head;
    }
};

There’s a shorter way to write the same walk. Instead of tracking the last node kept, sit on a node and look one ahead, unlinking the neighbour while it matches:

ListNode* deleteDuplicates(ListNode* head) {
    ListNode* curr = head;
    while (curr && curr->next) {
        if (curr->val == curr->next->val) curr->next = curr->next->next;
        else curr = curr->next;
    }
    return head;
}
  • time: O(n) - each node is looked at once
  • space: O(1) - two pointers, nodes are relinked in place

Note: neither version frees the skipped nodes. Leetcode doesn’t care, but outside it you’d hold the duplicate in a temporary and delete it after relinking.

quantinium © 2026