Problem statement

You are given the head of a singly linked list sorted in non-decreasing order. Delete nodes so that every value appears exactly once, and return the head of the list, which stays sorted.

Example 1

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

Example 2

Input: head = [1,1,2,3,3]
Output: [1,2,3]
Explanation: One node of each value is kept; the list is still sorted.

Example 3

Input: head = []
Output: []

Constraints

• The number of nodes in the list is in the range [0, 300]
• -100 <= Node.val <= 100
• The list is sorted in non-decreasing order

Hints for Remove Duplicates from Sorted List

1. Hint 1

   In a sorted list, equal values sit next to each other.

2. Hint 2

   Walk the list once, comparing each node with the node after it.

3. Hint 3

   When the next node has the same value, unlink it (cur.next = cur.next.next) and stay put; otherwise move on.

How to solve Remove Duplicates from Sorted List

Sorting puts all copies of a value in one consecutive run, so a duplicate is always the immediate successor of a node with the same value. Unlinking such successors in a single pass leaves one node per run.

Approach

1. Set cur = head.
2. While cur and cur.next exist: if cur.next.val == cur.val, skip it with cur.next = cur.next.next; otherwise advance cur = cur.next.
3. Return head.

Why it works

cur only advances to a node with a new value, and before it does, every following node equal to cur has been unlinked. So each run collapses to its first node and nothing else is removed.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Do not advance cur after removing a duplicate — the new cur.next may be another copy.
• Handle the empty list: the loop must not touch head.next when head is null.

Reference solution

Python

from typing import Optional

def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
    cur = head
    while cur and cur.next:
        if cur.next.val == cur.val:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return head

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More two pointers problems

• Nth Node From End of Linked List Easy
• Intersection of Two Sorted Linked Lists Easy
• Middle of the Linked List Easy
• Palindrome Linked List Easy
• Merge Two Sorted Lists Easy
• Two Sum IV - Input is a BST Easy