CA 23 - Remove Duplicates in Sorted Linked List

Problem
Remove Duplicates in Sorted Linked List
You are given a sorted singly linked list.
Your task is to remove duplicate nodes, keeping only one occurrence of each element.

The solution should be done in-place with O(1) extra space.

Examples
Input: 2 → 2 → 4 → 5
Output: 2 → 4 → 5
Input: 2 → 2 → 2 → 2 → 2
Output: 2

Approach

Since the list is already sorted, duplicate values will always be adjacent.

Steps:

• Traverse the list using a pointer curr
• Compare the current node with the next node:
• If they are equal → skip the next node (curr.next = curr.next.next)
• Otherwise → move to the next node
• Continue until the end of the list

This removes duplicates without using extra space.

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

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = nex
def removeDuplicates(head):
    curr = head
    while curr and curr.next:
        if curr.val == curr.next.val:
            curr.next = curr.next.next
        else:
            curr = curr.next
    return head
head = ListNode(2)
head.next = ListNode(2)
head.next.next = ListNode(4)
head.next.next.next = ListNode(5)

new_head = removeDuplicates(head)

curr = new_head
while curr:
    print(curr.val, end=" -> " if curr.next else "")
    curr = curr.next