We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Duplicates from Sorted List

Difficulty: Easy

Problem Description

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.

Key Insights

  • The linked list is sorted, which allows us to efficiently identify duplicates by comparing adjacent nodes.
  • We can use a single pointer to traverse the list and modify the links as we find duplicates.
  • The constraints ensure that the number of nodes is manageable, allowing for a straightforward linear traversal approach.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list once. Space Complexity: O(1), since we only use a constant amount of extra space for pointers.

Solution

To solve the problem, we will use a single pointer to traverse the linked list. We will compare each node with its next node. If they have the same value, we will skip the next node by updating the current node's next pointer. This approach ensures that we only keep unique values in the list while maintaining the order since the list is already sorted.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteDuplicates(head: ListNode) -> ListNode:
    current = head  # Start with the head of the list
    while current and current.next:  # Traverse until the end of the list
        if current.val == current.next.val:  # Check for duplicates
            current.next = current.next.next  # Skip the next node
        else:
            current = current.next  # Move to the next node
    return head  # Return the modified list
← Back to All Questions