Remove Duplicates from Sorted List II

📋

Problem

Imagine cleaning up a sorted contact list where duplicate entries must be completely removed, not just reduced to one.

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

The number of nodes in the list is in the range [0, 10^5].The list is sorted in ascending order.Node values are integers within the 32-bit signed integer range.

Edge cases: Empty list → returns empty listAll nodes are duplicates → returns empty listDuplicates at the start → correctly removes initial nodes

</>

IDE

def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:public ListNode deleteDuplicates(ListNode head)ListNode* deleteDuplicates(ListNode* head)function deleteDuplicates(head)

def deleteDuplicates(head):
    # Write your solution here
    pass

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* deleteDuplicates(ListNode* head) {
    // Write your solution here
    return nullptr;
}

function deleteDuplicates(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 2, 3, 3, 4, 4, 5]No duplicates removed; code fails to detect or skip duplicates.✅ Add logic to detect duplicate runs and skip all nodes with duplicate values before linking.

Wrong: [1, 2, 3, 4, 5]Only one instance of duplicates removed instead of all; partial removal.✅ Use a while loop to skip all nodes with the same duplicate value, not just one.

Wrong: [1, 1, 2, 3, 3]Duplicates at start and end not removed; dummy head not used or prev pointer mismanaged.✅ Use dummy head and carefully update prev.next after skipping duplicates.

Wrong: [1]Single node removed incorrectly; code removes nodes without checking duplicates.✅ Only remove nodes if duplicates detected; otherwise return head as is.

Wrong: Timeout or crash on large inputInefficient nested loops causing O(n^2) complexity or stack overflow in recursion.✅ Implement single pass iterative solution with dummy head to achieve O(n) time complexity.

✓

Test Cases

Focus on handling base cases like empty and single-node lists to build a robust solution.

Test your code against tricky cases with multiple duplicate runs and no duplicates to catch subtle bugs.

Optimize your solution to run in linear time by avoiding nested loops and using pointer tricks.

t1_01basic

Input{"head":[1,2,3,3,4,4,5]}

Expected[1,2,5]

⏱ Performance - must finish in 2000ms

Nodes with values 3 and 4 appear more than once and are completely removed.

💡 Focus on skipping all nodes that have duplicates, not just one occurrence.

💡 Use a dummy head and pointers to track previous and current nodes to remove duplicates.

💡 Advance current pointer past all duplicates before linking prev.next to current.

Why it failed: Output includes duplicate values or misses removing all duplicates. Fix by skipping entire runs of duplicate nodes using a while loop before linking.

✓ Correctly removes all duplicates and returns only distinct nodes.

t1_02basic

Input{"head":[1,1,2,3,3]}

Expected[2]

⏱ Performance - must finish in 2000ms

Values 1 and 3 appear more than once and are removed, leaving only 2.

💡 Check for duplicates at the start and end of the list.

💡 Ensure dummy head handles duplicates at the head correctly.

💡 Skip all nodes with duplicate values before linking prev.next.

Why it failed: Fails to remove duplicates at the start or end, leaving duplicate nodes in output. Fix by always using dummy head and skipping all duplicates before linking.

✓ Properly removes duplicates at list boundaries.

t2_01edge

Input{"head":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty list input returns empty list output.

💡 Consider the case when head is None or empty.

💡 Your code should handle empty input without errors.

💡 Return head immediately if it is None.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by checking if head is None at start and returning it.

✓ Handles empty input gracefully.

t2_02edge

Input{"head":[1]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node list with no duplicates returns the node itself.

💡 Check behavior when list has only one node.

💡 No duplicates possible, so return head as is.

💡 Ensure no unnecessary removals or pointer changes.

Why it failed: Incorrectly removes single node or returns empty list. Fix by not removing nodes unless duplicates are detected.

✓ Correctly returns single node list unchanged.

t2_03edge

Input{"head":[1,1,1,1]}

Expected[]

⏱ Performance - must finish in 2000ms

All nodes are duplicates, so entire list is removed.

💡 Handle case where all nodes have the same value.

💡 Skip entire list if all nodes are duplicates.

💡 Use dummy head to unlink all nodes if duplicates span entire list.

Why it failed: Returns non-empty list when all nodes are duplicates. Fix by skipping all nodes with duplicate values before linking.

✓ Removes all duplicates leaving empty list.

t3_01corner

Input{"head":[1,2,2,3,4,4,5]}

Expected[1,3,5]

⏱ Performance - must finish in 2000ms

Duplicates 2 and 4 removed; distinct nodes remain.

💡 Beware of off-by-one errors when skipping duplicates.

💡 Ensure you move current pointer past all duplicates before linking.

💡 Use a while loop to skip all nodes with the same duplicate value.

Why it failed: Output includes one instance of duplicates due to off-by-one skip. Fix by fully skipping all nodes with duplicate values before linking.

✓ Correctly removes all duplicates without leaving any behind.

t3_02corner

Input{"head":[1,1,2,3,3,4,5,5]}

Expected[2,4]

⏱ Performance - must finish in 2000ms

Duplicates 1, 3, and 5 removed; only 2 and 4 remain.

💡 Check that duplicates at multiple separated positions are all removed.

💡 Do not stop skipping after first duplicate run; continue through list.

💡 Maintain prev pointer correctly to link only distinct nodes.

Why it failed: Fails to remove all duplicate runs, leaving some duplicates in output. Fix by continuing to skip duplicates throughout entire list.

✓ All duplicate runs removed correctly.

t3_03corner

Input{"head":[1,2,3,4,5]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

No duplicates present; list remains unchanged.

💡 Verify that your code does not remove unique nodes.

💡 Check that prev pointer advances correctly when no duplicates.

💡 Return original list if no duplicates found.

Why it failed: Incorrectly removes unique nodes or returns empty list. Fix by only removing nodes when duplicates detected.

✓ Leaves unique nodes intact as expected.

t4_01performance

Input{"head":[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48,49,49,50,50]}

Expected[]

⏱ Performance - must finish in 2000ms

n=100 nodes with all duplicates; O(n) solution must complete within 2 seconds.

💡 Use a single pass with dummy head to remove duplicates efficiently.

💡 Avoid nested loops to prevent O(n^2) time complexity.

💡 Skip entire duplicate runs in one pass to maintain O(n) complexity.

Why it failed: Solution times out due to nested loops or repeated scanning. Fix by implementing single pass skipping duplicates with dummy head.

✓ Solution runs in O(n) time confirming efficient complexity.

Practice

1. You are given a singly linked list and two positions left and right. The task is to reverse the nodes of the list from position left to right in-place and return the modified list. Which approach guarantees an optimal solution with O(n) time and O(n) space complexity?

easy

A. Extract the sublist, reverse it separately, then reattach it to the original list.

B. Use dynamic programming to store reversed sublists and combine them efficiently.

C. Use a recursive approach that reverses the first n nodes and recursively adjusts the rest.

D. Apply a greedy approach that swaps node values between left and right positions.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reversing a sublist in-place between two given positions, which suggests a partial reversal rather than full list reversal.

2. Step 2: Identify the approach that fits the constraints

   The recursive approach reverses the first n nodes and uses recursion to handle the rest, achieving O(n) time and O(n) space due to recursion stack, which is optimal for this problem.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursive reversal matches problem constraints and complexity [OK]

Hint: Partial recursive reversal fits sublist reversal best [OK]

Common Mistakes:

• Thinking greedy swaps node values suffice
• Assuming dynamic programming applies to linked list reversal
• Believing extraction and rebuild is optimal

2. You are given a singly linked list and asked to reverse it in-place, such that the last node becomes the head and all pointers are reversed. Which approach guarantees an optimal solution with O(n) time and O(n) space complexity, avoiding stack overflow on large inputs?

easy

A. Use a brute force recursive reversal that reverses pointers on the way back up the call stack.

B. Use dynamic programming to store reversed sublists and combine them to form the reversed list.

C. Use a greedy approach that swaps node values instead of pointers to reverse the list.

D. Use a tail-recursive helper function that passes previous and current nodes, reversing pointers during the recursive descent.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reversing a singly linked list in-place, which means changing the next pointers without extra data structures.

2. Step 2: Evaluate approaches

   The brute force recursive reversal (A) uses recursion but reverses pointers on the return path, risking stack overflow and extra space. The greedy approach (C) swaps values, which is not pointer reversal and may not be allowed. Dynamic programming (D) is not applicable here. The tail-recursive helper function (B) reverses pointers during recursion descent, maintaining O(n) time and O(n) space due to recursion stack, and is optimal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Tail recursion with prev and curr pointers ensures correct reversal [OK]

Hint: Tail recursion reverses pointers during descent [OK]

Common Mistakes:

• Confusing value swapping with pointer reversal
• Using naive recursion causing stack overflow

3. What is the time complexity of the optimal in-place algorithm that removes duplicates from a sorted singly linked list by iterating once and adjusting pointers?

medium

A. O(n), since each node is visited at most once in a single pass

B. O(1), because only pointer adjustments are made

C. O(n log n), due to sorting or recursive calls involved

D. O(n²), because each removal requires scanning the rest of the list

Solution

1. Step 1: Identify the number of iterations

   The algorithm visits each node once, moving forward only when no duplicate is found.

2. Step 2: Analyze pointer adjustments

   Pointer changes happen in constant time per duplicate removal, no nested loops or recursion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single linear pass over n nodes -> O(n) time [OK]

Hint: Single pass over list nodes -> linear time [OK]

Common Mistakes:

• Confusing with nested loops or sorting complexity

4. Identify the bug in the following tail-recursive reversal code snippet:

def reverseList(head):
    def helper(prev, curr):
        if not curr:
            return prev
        curr.next = prev
        next_temp = curr.next
        return helper(curr, next_temp)
    return helper(None, head)

medium

A. Line 3: Base case should check if prev is None instead of curr.

B. Line 6: The recursive call should pass next_temp as prev instead of curr.

C. Line 5: next_temp is assigned after curr.next is changed, losing original next node.

D. Line 2: The helper function should be iterative, not recursive.

Solution

1. Step 1: Analyze pointer updates

   Line 5 assigns next_temp = curr.next after curr.next is set to prev, so next_temp points to prev, not the original next node.

2. Step 2: Consequence of bug

   Because next_temp is incorrect, recursion loses the rest of the list, causing incomplete reversal or infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Saving next node before pointer reversal is critical [OK]

Hint: Always save next node before changing curr.next [OK]

Common Mistakes:

• Swapping order of pointer updates
• Forgetting to set head.next to None in recursion

5. Suppose the linked list rotation problem is modified so that k can be negative, indicating rotation to the left by |k| places. Which modification to the optimal algorithm correctly handles negative k values?

hard

A. Ignore negative k and return the original list without rotation.

B. Convert negative k to positive by k = abs(k) and rotate right as usual.

C. Adjust k by k = (k % length + length) % length to normalize negative rotations to equivalent right rotations.

D. Reverse the list first, then apply the original rotation algorithm with positive k.

Solution

1. Step 1: Understand negative rotation meaning

   Negative k means rotate left by |k|, which is equivalent to rotating right by length - |k|.

2. Step 2: Normalize k to positive equivalent

   Using k = (k % length + length) % length converts negative k to correct positive rotation count.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Normalization handles negative rotations correctly [OK]

Hint: Normalize k with modulo to handle negatives [OK]

Common Mistakes:

• Taking absolute value loses rotation direction
• Ignoring negative k leads to wrong output
• Reversing list unnecessarily complicates solution