LeetCode Solutions Blog

Remove Duplicates from Sorted List

Number: 83

Difficulty: Easy

Paid? No

Problem Description

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

Key Insights

The linked list is already sorted, so any duplicates will be adjacent.
A single pass through the list is sufficient to remove duplicates.
The algorithm modifies the list in place without needing extra memory.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the list
Space Complexity: O(1) - in-place modification with constant extra space

Solution

We traverse the linked list using a pointer. For each node, we check if the next node has the same value. If it does, we adjust the pointer to skip the duplicate node. Otherwise, we move our pointer to the next node. This approach efficiently removes duplicates in a single pass without requiring additional data structures.

Code Solutions

# 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: ListNode) -> ListNode:
        # Initialize current pointer to head of the list
        current = head
        # Traverse until we reach the end of the list
        while current and current.next:
            # If duplicate is found, skip the next node
            if current.val == current.next.val:
                current.next = current.next.next  # Remove duplicate by linking to the next distinct node
            else:
                current = current.next  # Move to next node if current and next values are distinct
        return head