Remove Duplicates from a Sorted Linked List - CA23

My Thinking and Approach

Introduction

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

Since the list is sorted, duplicate values appear next to each other.

Problem Statement

Given the head of a sorted linked list
Remove duplicate nodes
Return the updated list
Conditions:
- Do not use extra space
- Maintain original order

My Initial Thought

At first, I considered:

Using a set to store values
Rebuilding the list with unique elements

But this approach uses extra space.

Key Observation

Because the list is sorted:

Duplicate elements are adjacent
I only need to compare current node with next node

Optimized Approach

I decided to traverse the list once and remove duplicates in-place.

Logic:

If current node value equals next node value → skip the next node
Else → move forward

My Approach (Step-by-Step)

Start with curr = head
Traverse while curr and curr.next exist
At each step:

If curr.data == curr.next.data → remove duplicate → curr.next = curr.next.next
Else → move to next node

Code (Python)

Below is the implementation clearly separated inside a code block:

```python id="k9f2xw"
class Node:
def init(self, data):
self.data = data
self.next = None

class Solution:
def removeDuplicates(self, head):
curr = head

    while curr and curr.next:
        if curr.data == curr.next.data:
            curr.next = curr.next.next
        else:
            curr = curr.next

    return head




---

## Example Walkthrough

### Input:



```text id="x6p3lm"
2 -> 2 -> 4 -> 5

Steps:

Compare 2 and 2 → remove duplicate
Move forward and compare remaining nodes

Output:

```text id="r2g7zs"
2 -> 4 -> 5




---

## Complexity Analysis

| Type             | Complexity |
| ---------------- | ---------- |
| Time Complexity  | O(n)       |
| Space Complexity | O(1)       |

---

## Key Takeaways

* Sorted property simplifies the problem
* No extra space is required
* Pointer manipulation is important

---

## Conclusion

This problem helped me understand how to efficiently remove duplicates from a linked list using in-place operations.

---