Remove Duplicates From Sorted List

Problem Link

83. Remove Duplicates from Sorted List – LeetCode

Problem Statement

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.

Examples

Example 1:

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

Example 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 sorted in ascending order

Intuition

Since the list is already sorted, duplicate elements will always appear consecutively.
We just need to compare current node with the next node, and skip the next node if it's a duplicate.

Approach

Start from the head of the list.
While the current node and the next node are not null:
- If node.val == node.next.val, skip the next node by adjusting the pointer: node.next = node.next.next
- Else, move to the next node.
Return the head of the modified list.

Java Code

class Solution {
    public ListNode deleteDuplicates(ListNode node) {
        if (node == null) return null;

        ListNode head = node;

        while (node.next != null) {
            if (node.val == node.next.val) {
                node.next = node.next.next; // Skip the duplicate
            } else {
                node = node.next; // Move to next distinct node
            }
        }

        return head;
    }
}

Time and Space Complexity

Metric	Value
Time Complexity	O(n)
Space Complexity	O(1)
Explanation	Only one pass through the list, no extra memory used

Dry Run

Input:

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

Step-by-step:

Compare 1 and 1 → duplicate → skip next
Now compare 1 and 2 → move ahead
Compare 2 and 3 → move ahead
Compare 3 and 3 → duplicate → skip next

Final list: [1,2,3]

Conclusion

This problem demonstrates a classic use of pointer manipulation in singly linked lists. Since the list is sorted, the solution becomes simple and efficient using a single traversal.