Remove Duplicates from a Sorted Linked List –CA23

My Thinking and Approach

Introduction

In this problem, I was given a sorted linked list and asked to remove duplicate elements.

Since the list is already sorted, duplicates will always appear next to each other. This made the problem easier to approach.

---

Problem Statement

• Given a sorted linked list
• Remove duplicate nodes
• Return the updated list

---

My Initial Thought

Initially, I thought:

• Store elements in a set
• Rebuild the linked list

But this uses extra space, which is not required here.

---

Key Observation

Because the list is sorted:

• Duplicate values are always adjacent
• So I only need to compare current node with the next node

---

Optimized Approach

I decided to:

• Traverse the list once

• If current node value equals next node value:

  • Skip the next node

• Otherwise:

  • Move forward

---

My Approach

• Start with curr = head
• Traverse while curr and curr.next are not null

Steps:

1. If curr.data == curr.next.data:

• Remove duplicate by skipping node
• curr.next = curr.next.next

1. Else:

• Move to next node

---

Code (Java)

class Solution {
    Node removeDuplicates(Node head) {
        Node curr = head;

        while (curr != null && curr.next != null) {
            if (curr.data == curr.next.data) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }

        return head;
    }
}

---

Example Walkthrough

Example

Input:
2 → 2 → 4 → 5

Steps:

• Compare 2 and 2 → remove duplicate
• List becomes → 2 → 4 → 5

Output:
2 → 4 → 5

---

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Key Takeaways

• Sorted property simplifies the problem
• No need for extra space
• Pointer manipulation is important in linked lists

---

Conclusion

This problem helped me understand how to efficiently handle duplicates in linked lists. It also reinforced the importance of using problem constraints (like sorted order) to simplify the solution.