ASSIGNMENT 23

1. Remove Duplicates From a Sorted Linked List

Problem

Given a sorted singly linked list, remove all duplicate nodes so that each element appears only once.

Example

Input:
2 → 2 → 4 → 5

Output:
2 → 4 → 5

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

Approach Used

Iterative Approach (Optimal)

We traverse the linked list and:

•Compare each node with its next node
•If both values are same → remove duplicate
•Otherwise → move forward

👉 This works efficiently because duplicates are adjacent in sorted list 

Step-by-Step Explanation

Step 1: Start from Head

Step 2: Traverse the List

Step 3: Check for Duplicate

Remove Duplicate

If duplicate found
•Skip the next node

Step 5: Move Forward

•Compare 2 & 2 → duplicate → remove
→ 2 → 2 → 4 → 5
•Compare 2 & 2 → duplicate → remove
→ 2 → 4 → 5
•Compare 2 & 4 → not duplicate → move forward
•Compare 4 & 5 → not duplicate → move forward

CODE:

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

    while curr is not None and curr.next is not None:
        if curr.data == curr.next.data:
            curr.next = curr.next.next   
        else:
            curr = curr.next            

    return head`

Complexity Analysis

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

Conclusion

Removing duplicates from a sorted linked list is straightforward because duplicates appear consecutively. By simply comparing each node with its next and adjusting pointers, we can remove duplicates efficiently.