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

Remove Duplicates from Sorted List II (LeetCode #82) 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 linked list is sorted, which allows us to easily identify duplicates by comparing adjacent nodes.

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

The optimal solution for Remove Duplicates from Sorted List II runs in O(n) time and uses O(1) space. This complexity is linear because we only traverse the list once, making it much more efficient than the brute force approach.

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

The brute force approach for Remove Duplicates from Sorted List II is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we traverse the linked list and for each node, we check if it has duplicates. If it does, we skip those nodes. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

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

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

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

Always consider edge cases, such as empty lists or lists with all duplicates. Explain your thought process clearly while coding; it helps the interviewer understand your approach. Practice writing clean and efficient code, as readability is important in interviews.

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

Not handling the case where the head node itself is a duplicate. Failing to update the previous pointer correctly when duplicates are found.

#82

Remove Duplicates from Sorted List II

Medium

Linked ListTwo PointersTwo PointersLinked List Manipulation

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)

This approach uses a dummy node and a single pass through the list to efficiently remove duplicates. By keeping track of the previous node, we can easily skip over duplicates without needing nested loops.

⚙️

Algorithm

6 steps

1Step 1: Create a dummy node that points to the head of the list.
2Step 2: Initialize two pointers: prev (to track the last unique node) and current (to traverse the list).
3Step 3: Traverse the list while checking for duplicates.
4Step 4: If duplicates are found, skip all of them by advancing current.
5Step 5: If no duplicates are found, move prev to current.
6Step 6: Continue until the end of the list and return dummy.next.

solution.py20 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    dummy = ListNode(0)
9    dummy.next = head
10    prev = dummy
11    current = head
12    while current:
13        if current.next and current.val == current.next.val:
14            while current.next and current.val == current.next.val:
15                current = current.next
16            prev.next = current.next
17        else:
18            prev = prev.next
19        current = current.next
20    return dummy.next

ℹ

Complexity note: This complexity is linear because we only traverse the list once, making it much more efficient than the brute force approach.

1The linked list is sorted, which allows us to easily identify duplicates by comparing adjacent nodes.
2Using a dummy node simplifies edge cases, such as when the head itself is a duplicate.

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