83. Remove Duplicates from Sorted List - Detailed Explanation

Problem Statement

You’re given the head of a sorted singly linked list. Remove all duplicates in place so that each element appears only once, and return the head of the updated list.

Examples

Example 1

Input   head = [1,1,2]  
Output  [1,2]  
Explanation  You start with 1→1→2. You remove the second `1` so it becomes 1→2.

Example 2

Input   head = [1,1,2,3,3]  
Output  [1,2,3]  
Explanation  Duplicates of `1` and `3` are removed.

Example 3

Input   head = [1,1,1,1]  
Output  [1]  
Explanation  All extra `1`s are removed, leaving a single node.

Constraints

The number of nodes is in [0, 300]
-100 ≤ Node.val ≤ 100
The list is sorted in non‑decreasing order

Hints

How can you traverse the list so that when you see a run of equal values you skip over the extras?
What pointers do you need to remember as you unlink duplicate nodes?

Approach 1 using Auxiliary Storage

Idea

Build a new list (or array) of unique values by scanning the original. Then reconstruct a linked list from those values.

Steps

Traverse the original list, appending each new value to a Python list (or Java List<Integer>) only when it differs from the last added.
Create a fresh linked list from that unique‑value list.
Return its head.

Code (Python)

Python3

. . . .

Java Code

Java

. . . .

Approach 2 In‑Place One‑Pass

Idea

Because the list is sorted, all duplicates are consecutive. Use two pointers:

current scans node by node.
When current.next.val == current.val, unlink current.next.
Otherwise advance current.

Steps

If head is null, return it.
Let current = head.
While current.next exists:
- If current.next.val == current.val, do current.next = current.next.next (skip duplicate).
- Else current = current.next.
Return head.

Code (Python)

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time O(n) since each node is visited at most once.
Space O(1) extra for the in‑place approach (≈O(n) if you rebuild with extra storage).

Step‑by‑Step Walkthrough

Consider 1→1→2→3→3 with the in‑place approach:

curr at first 1. curr.next.val also 1 → unlink second 1. List becomes 1→2→3→3.
curr still at 1. Now curr.next.val is 2 → move curr to node 2.
At 2, curr.next.val is 3 → move curr to 3.
At first 3, curr.next.val is 3 → unlink second 3. List becomes 1→2→3.
curr.next is now null → done.

Common Mistakes

Forgetting to check curr for null before accessing curr.next.
Skipping the else curr = curr.next step, causing infinite loop on duplicates.
Using a fresh head pointer in recursion (overkill here).

Edge Cases

Empty list head = null.
Single‑node list.
No duplicates at all.
All nodes identical.

Alternative Variations

Remove duplicates II (LeetCode 82): delete all nodes that have duplicate numbers, leaving only distinct values.
Allow each value at most k times (e.g. LeetCode 80 for arrays).
Remove duplicates from unsorted list (requires hashing).

26. Remove Duplicates from Sorted Array – In-place remove duplicates in a sorted array, return the new length.
19. Remove Nth Node From End of List – Delete the nᵗʰ node from the end in one pass.
141. Linked List Cycle – Detect whether a singly linked list has a cycle.
430. Flatten a Multilevel Doubly Linked List – Flatten a multilevel doubly linked list into a single‐level list.