Remove Duplicates from Sorted List

Share

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.

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

Solution Approach - Single Pass

Since the list is sorted, all duplicate values are adjacent. We can traverse the list once, and whenever the current node's value equals the next node's value, we skip the next node by updating the next pointer.

  • Start with curr = head.
  • While curr != null and curr.next != null:
  • If curr.val == curr.next.val, skip the next node: set curr.next = curr.next.next.
  • Otherwise, advance curr = curr.next.
  • Return head.
Java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class RemoveDuplicatesFromSortedList {

    public ListNode deleteDuplicates(ListNode head) {
        ListNode curr = head;

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

        return head;
    }
}
Complexity Analysis:

Time complexity: O(n) where n is the length of the list. Each node is visited at most once.
Space complexity: O(1) as only a single pointer is used for traversal.