Leetcode 83: Remove Duplicates from Sorted List

 

1. Problem Statement (Simple Explanation)

You’re given the head of a sorted singly linked list.

You must:

• Remove duplicate nodes so that each value appears only once.

• Keep the list sorted.

• Return the head of the resulting list.

Unlike Problem 82, here you keep one copy of each value and delete the extra nodes.

2. Examples

Example 1:

Input: head = [1,1,2]

• 1 appears twice → keep one.

• 2 appears once.

Output: [1,2]

Example 2:

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

• 1 appears twice → keep one.

• 2 appears once.

• 3 appears twice → keep one.

Output: [1,2,3]

3. Approach – One Pass, O(1) Space

The list is sorted, so duplicates are adjacent.

We can scan through the list with a pointer curr:

1. Start curr = head.

2. While curr is not null and curr.next is not null:

• If curr.val == curr.next.val:

• We have a duplicate node.

• Remove it by:

curr.next = curr.next.next

• Do not advance curr in this case; we might still have more duplicates with the same value.

• Else:

• Move curr = curr.next (go to next distinct value).

At the end, head points to the de-duplicated sorted list.

Pseudo-code:

Complexity:

Let n = number of nodes.

• Time: O(n) – each node is visited at most once.

• Space: O(1) extra – in-place.

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code