Removing Duplicates from a Sorted Linked List in Python

Problem Explanation

You are given a sorted singly linked list.
Your task is to remove duplicate nodes so that each element appears only once.

Since the list is sorted, duplicate elements will be next to each other.

Example:

• Input: 2 → 2 → 4 → 5 Output: 2 → 4 → 5

---

Method Used: Iterative Traversal

Idea

• Traverse the linked list
• Compare current node with next node
• If values are same → skip the next node

---

Why This Method?

• Time complexity: O(n)
• Space complexity: O(1)
• No extra data structures needed
• Works efficiently because list is sorted

---

Python Code with Explanation

def removeDuplicates(head):

Defines the function. head is the start of the linked list.

---

    curr = head

Start from the first node.

---

    while curr and curr.next:

Loop until we reach the end of the list.

---

        if curr.data == curr.next.data:

Check if current node and next node have the same value.

---

            curr.next = curr.next.next

Skip the duplicate node by changing the pointer.

---

        else:
            curr = curr.next

If not duplicate, move to next node.

---

    return head

Return the updated linked list.

---

Complete Code

def removeDuplicates(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

---

Step-by-Step Example

Input:

2 → 2 → 4 → 5

Steps:

• Compare 2 and 2 → remove duplicate
• Move forward
• No more duplicates

Output:

2 → 4 → 5

---

Key Takeaway

Because the list is sorted, duplicates are adjacent, making it easy to remove them in a single pass without extra memory.

---