Taro Logo

Remove Duplicates from Sorted List

Easy
Revolut logo
Revolut
1 view
Topics:
Linked Lists

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.

Example 1:

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

Example 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.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Can the linked list be empty, or will it always contain at least one node?
  2. What is the range of values for the nodes in the linked list?
  3. Is the input list guaranteed to be sorted in ascending order, or do I need to handle unsorted input?
  4. Should I modify the values of the existing nodes, or can I create new nodes?
  5. What should I return if the input list is null?

Brute Force Solution

Approach

The brute force method for removing duplicates in a sorted list is like checking every single value against every other value. We painstakingly compare each item to all subsequent items to identify and handle duplicates. It's a thorough but inefficient way to solve the problem.

Here's how the algorithm would work step-by-step:

  1. Start with the first item in the list.
  2. Compare it to every item that comes after it in the list.
  3. If you find an item that is the same, remove the duplicate from the list.
  4. Move to the next item in the original list.
  5. Repeat the comparison process, comparing the current item to all the items that follow it.
  6. Continue this process until you have compared every item to all the items that come after it.
  7. The result will be a list with all duplicates removed.

Code Implementation

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

def remove_duplicates_brute_force(head):
    current_node = head

    while current_node:
        # Iterate through the rest of the list for each node.
        runner_node = current_node
        while runner_node.next:
            if current_node.val == runner_node.next.val:
                # Remove the duplicate node
                runner_node.next = runner_node.next.next

            else:
                runner_node = runner_node.next

        # Advance current_node to the next unique node.
        current_node = current_node.next

    return head

Big(O) Analysis

Time Complexity
O(n²)The provided brute force solution iterates through the linked list. For each node in the list of size n, the algorithm potentially compares it to all subsequent nodes. In the worst case, this involves roughly (n-1) comparisons for the first element, (n-2) for the second, and so on, down to 0 for the last element. This leads to a total number of comparisons approximating n * (n-1) / 2. Dropping the lower order terms and constant factors, the time complexity is O(n²).
Space Complexity
O(1)The provided brute force algorithm operates directly on the input list. While it modifies the original list in place to remove duplicates, it doesn't create any auxiliary data structures such as temporary lists, sets, or hash maps to store elements or track visited nodes. The algorithm only uses a constant number of variables for iteration and comparison. Therefore, the space complexity remains constant irrespective of the input size N (the number of elements in the list).

Optimal Solution

Approach

Since the list is sorted, we can solve this problem efficiently by traversing it only once. We just need to keep track of the last unique element we've seen and remove any subsequent duplicates we encounter.

Here's how the algorithm would work step-by-step:

  1. Begin by examining the first item in the list. This item is, by default, considered a unique item.
  2. Compare the current item with the next item in the list.
  3. If the next item is identical to the current item, remove the next item from the list. Continue doing this until you encounter a different item.
  4. If the next item is different from the current item, move your focus to the next item (the new unique one).
  5. Repeat steps 2-4 until you reach the end of the list.

Code Implementation

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

def remove_duplicates_from_sorted_list(head):
    if not head:
        return head

    current_node = head

    while current_node.next:
        # Compare current node to the next
        if current_node.value == current_node.next.value:

            # Remove the duplicate node
            current_node.next = current_node.next.next

        else:
            # Move to the next unique node
            current_node = current_node.next

    return head

Big(O) Analysis

Time Complexity
O(n)The algorithm iterates through the sorted linked list of size n, examining each node to determine if it's a duplicate. For each node, it might remove subsequent duplicate nodes, but these removals are done in constant time. Thus, the dominant operation is the single pass through the list, resulting in a linear time complexity of O(n).
Space Complexity
O(1)The algorithm operates in-place, modifying the original linked list directly. It only requires a constant amount of extra space to store pointers or references to the current and next nodes while traversing the list. Therefore, the auxiliary space used does not depend on the size of the input list, N, and remains constant. The space complexity is O(1).

Edge Cases

CaseHow to Handle
Empty list (head is null)Return null immediately as there's nothing to process.
List with only one nodeReturn the head as is, since there are no duplicates possible.
List with all nodes having the same valueThe algorithm should reduce the list to a single node with that value.
List with consecutive duplicate values at the beginningThe algorithm should correctly skip all initial duplicates.
List with consecutive duplicate values in the middleThe algorithm should correctly skip all middle duplicates while maintaining the sorted order.
List with consecutive duplicate values at the endThe algorithm should correctly remove trailing duplicates and terminate the list properly.
Large list (potential performance concerns)The iterative approach maintains O(n) time complexity, which scales linearly, but recursion could lead to stack overflow.
Negative and positive values intermixed with duplicatesSince the list is sorted, the algorithm handles both negative and positive values equally by comparing adjacent nodes.