Remove Duplicates from Sorted List

Difficulty: Easy | Acceptance: 56.70% | Paid: No Topics: Linked List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

• Examples
• Constraints
• Iterative Approach
• Recursive Approach

Examples

Input: head = [1,1,2]
Output: [1,2]

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Constraints

The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.

Iterative Approach

Intuition Since the list is sorted, duplicate nodes must be adjacent. We can iterate through the list and remove the next node whenever its value is the same as the current node.

Steps

• Initialize a pointer current at the head of the list.
• Traverse the list while current and current.next are not null.
• If current.val equals current.next.val, bypass the duplicate by setting current.next to current.next.next.
• Otherwise, move the current pointer forward.
• Return the modified list head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        current = head
        while current and current.next:
            if current.val == current.next.val:
                current.next = current.next.next
            else:
                current = current.next
        return head

Complexity

• Time: O(n)
• Space: O(1)
• Notes: We only modify pointers in place, requiring constant extra memory.

Recursive Approach

Intuition Recursively process the list starting from the second node. If the head node’s value matches the new head of the processed sublist, we skip the head node; otherwise, we keep it.

Steps

• Base case: If head is null or head.next is null, return head.
• Recursively call deleteDuplicates on head.next and assign the result to head.next.
• If head.val equals head.next.val, return head.next (effectively removing the duplicate head).
• Otherwise, return head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        head.next = self.deleteDuplicates(head.next)
        if head.val == head.next.val:
            return head.next
        return head

Complexity

• Time: O(n)
• Space: O(n)
• Notes: The recursion stack uses space proportional to the length of the list.