How do you solve Remove Duplicates from Sorted List on LeetCode?

Remove Duplicates from Sorted List (LeetCode #83) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The list is sorted, allowing for a single pass to remove duplicates.

What is the time complexity of Remove Duplicates from Sorted List?

The optimal solution for Remove Duplicates from Sorted List runs in O(n) time and uses O(1) space. This complexity is linear because we only traverse the list once, checking each node and its next node.

What is the brute force solution for Remove Duplicates from Sorted List?

The brute force approach for Remove Duplicates from Sorted List is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves comparing each node with every other node to find duplicates. Since the list is sorted, we can simply traverse the list and remove duplicates as we encounter them. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Remove Duplicates from Sorted List?

Remove Duplicates from Sorted List uses the following concepts: Linked List. The recommended patterns to study are: Two Pointers, Linked List.

What are the interview tips for Remove Duplicates from Sorted List?

Clarify the input constraints (sorted list). Explain your thought process while coding. Test your code with edge cases before finalizing.

What are common mistakes when solving Remove Duplicates from Sorted List?

Not handling the edge case of an empty list. Forgetting to update the current pointer correctly.

#83

Remove Duplicates from Sorted List

Easy

Linked ListTwo PointersLinked List

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages the fact that the list is already sorted. By using a single pass through the list, we can efficiently remove duplicates without needing nested loops.

⚙️

Algorithm

5 steps

1Step 1: Initialize a pointer to the current node starting from the head.
2Step 2: While the current node and its next node are not null, check if the current node's value is the same as the next node's value.
3Step 3: If they are the same, skip the next node by pointing the current node's next to the next node's next.
4Step 4: If they are different, move the current pointer to the next node.
5Step 5: Continue until the end of the list.

solution.py14 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def deleteDuplicates(head):
8    current = head
9    while current and current.next:
10        if current.val == current.next.val:
11            current.next = current.next.next
12        else:
13            current = current.next
14    return head

ℹ

Complexity note: This complexity is linear because we only traverse the list once, checking each node and its next node.

1The list is sorted, allowing for a single pass to remove duplicates.
2Only adjacent duplicates need to be checked.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.