Remove Duplicates from Sorted List II

▶

Steps

setup

Initialize head pointer at first node

The algorithm starts with the head pointer at the first node with value 1. It checks if the list is empty or has only one node.

💡 This step sets the starting point for recursion and handles base cases.

Line:

if not head or not head.next:
    return head

💡 Base case check ensures recursion stops at list end or single node.

compare

Check if head has duplicates by comparing head.val and head.next.val

Compare the value of the current head node (1) with the next node (2) to detect duplicates.

💡 Detecting duplicates at the head is crucial to decide whether to skip nodes or keep the current node.

Line:

if head.val == head.next.val:

💡 Since head and next have different values, head is unique and should be kept.

traverse

Recurse on head.next to process the rest of the list

Since head is unique, the algorithm calls deleteDuplicates recursively on the next node (value 2).

💡 Recursion breaks down the problem into smaller sublists, processing from left to right.

Line:

head.next = deleteDuplicates(head.next)

💡 The recursion will return a cleaned list starting from node with value 2.

compare

At node with value 2, check for duplicates with next node (3)

Compare current node value 2 with next node value 3 to detect duplicates.

💡 Checking duplicates at each node ensures all duplicate groups are detected.

Line:

if head.val == head.next.val:

💡 Node 2 is unique and will be kept.

traverse

Recurse on node with value 3 to process duplicates

Since node 2 is unique, recurse on node 3 to handle duplicates starting there.

💡 Recursion isolates the sublist starting at duplicates for removal.

Line:

head.next = deleteDuplicates(head.next)

💡 The recursion will handle duplicate nodes with value 3.

compare

Detect duplicates at node 3 by comparing with next node 3

Current node value 3 equals next node value 3, indicating duplicates.

💡 Detecting duplicates triggers skipping all nodes with this value.

Line:

if head.val == head.next.val:

💡 All nodes with value 3 must be removed.

shrink

Skip all nodes with value 3

Advance head pointer while nodes have value 3 to skip duplicates entirely.

💡 Skipping duplicates removes them from the final list.

Line:

val_to_remove = head.val
while head and head.val == val_to_remove:
    head = head.next

💡 Head moves past both nodes with value 3 to node with value 4.

traverse

Recurse on node with value 4 to remove duplicates

Call deleteDuplicates recursively on node 4 to handle duplicates starting there.

💡 Recursion continues to remove duplicates in the remaining list.

Line:

return deleteDuplicates(head)

💡 The recursion will remove duplicates with value 4.

compare

Detect duplicates at node 4 by comparing with next node 4

Current node value 4 equals next node value 4, indicating duplicates.

💡 Detecting duplicates triggers skipping all nodes with this value.

Line:

if head.val == head.next.val:

💡 All nodes with value 4 must be removed.

shrink

Skip all nodes with value 4

Advance head pointer while nodes have value 4 to skip duplicates entirely.

💡 Skipping duplicates removes them from the final list.

Line:

val_to_remove = head.val
while head and head.val == val_to_remove:
    head = head.next

💡 Head moves past both nodes with value 4 to node with value 5.

compare

At node with value 5, check for duplicates

Check if node 5 has duplicates by comparing with next node (null).

💡 Base case check for end of list or single node.

Line:

if not head or not head.next:
    return head

💡 Node 5 is unique and recursion returns this node.

reconstruct

Return node 5 as tail of cleaned list

Return node 5 as the cleaned list tail since no duplicates follow.

💡 Returning nodes up the recursion chain reconstructs the cleaned list.

Line:

return head

💡 Node 5 is confirmed unique and will be linked back up.

reconstruct

Link node 2's next to cleaned list starting at node 5

Return to node 2's recursion frame and link its next pointer to node 5, skipping duplicates.

💡 Reconstruction links unique nodes, skipping duplicates removed in recursion.

Line:

head.next = deleteDuplicates(head.next)
return head

💡 Node 2 now points directly to node 5, removing duplicates 3 and 4.

reconstruct

Link node 1's next to cleaned list starting at node 2

Return to node 1's recursion frame and link its next pointer to node 2, completing the cleaned list.

💡 Final reconstruction step links the head to the cleaned sublist.

Line:

head.next = deleteDuplicates(head.next)
return head

💡 Node 1 now points to node 2, completing the cleaned list [1,2,5].

final

Final cleaned list ready: [1, 2, 5]

The recursion completes and returns the head of the cleaned list with duplicates removed.

💡 The final list contains only unique nodes, confirming correctness.

Line:

return head

💡 The algorithm successfully removed all duplicates and returned the cleaned list.

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

def deleteDuplicates(head):
    # STEP 1: Base case check
    if not head or not head.next:
        return head
    # STEP 2: Check for duplicates at head
    if head.val == head.next.val:
        val_to_remove = head.val
        # STEP 3: Skip all duplicates
        while head and head.val == val_to_remove:
            head = head.next
        # STEP 4: Recurse on next distinct node
        return deleteDuplicates(head)
    else:
        # STEP 5: Recurse on next node and link
        head.next = deleteDuplicates(head.next)
        return head

# Driver code
if __name__ == '__main__':
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for v in arr:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

    def print_list(node):
        vals = []
        while node:
            vals.append(str(node.val))
            node = node.next
        print('[' + ','.join(vals) + ']')

    head = create_list([1,2,3,3,4,4,5])
    res = deleteDuplicates(head)
    print_list(res)  # Expected: [1,2,5]

📊

Remove Duplicates from Sorted List II - Watch the Algorithm Execute, Step by Step

Watching each pointer move and recursive call helps you understand how duplicates are skipped entirely and how the list is reconstructed without duplicates.

advance

1

→

2

→

3

→

3

→

4

→

4

→

5

compare

1

→

2

→

3

→

3

→

4

→

4

→

5

traverse

1

→

2

→

3

→

3

→

4

→

4

→

5

compare

1

→

2

→

3

→

3

→

4

→

4

→

5

traverse

2

→

3

→

3

→

4

→

4

→

5

compare

3

→

3

→

4

→

4

→

5

shrink

4

→

4

→

5

traverse

4

→

4

→

5

compare

4

→

4

→

5

shrink

5

compare

5

reconstruct

5

reconstruct

2

→

5

reconstruct

1

→

2

→

5

advance

1

→

2

→

5

Result: [1,2,5]

Key Takeaways

✓ The algorithm removes all nodes with duplicate values entirely, not just extra copies.

Reading code alone can confuse whether duplicates are removed or just reduced; visualization clarifies complete removal.

✓ Recursion breaks the problem into smaller sublists, making it easier to handle duplicates locally and reconstruct the list cleanly.

Understanding recursion flow is hard without seeing how each recursive call processes a sublist.

✓ Pointer skipping inside the while loop efficiently removes all duplicates of a value in one go.

Visualizing pointer moves shows how the algorithm jumps over duplicates instead of removing nodes one by one.

Practice

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

2. What is the time complexity of the two-pointer length equalization approach to find the intersection node of two singly linked lists with lengths m and n, respectively?

medium

A. O(m + n)

B. O(m * n)

C. O(max(m, n) * 2)

D. O(m + n + k), where k is the length of the intersection

Solution

1. Step 1: Identify loop iterations

   Each pointer traverses its list once, then switches to the other list, traversing at most m + n nodes.

2. Step 2: Simplify complexity

   Total steps are proportional to m + n, so time complexity is O(m + n). O(m * n) is brute force, O(max(m, n) * 2) simplifies to O(m + n), and O(m + n + k) adds an unnecessary term.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach is linear in combined list lengths [OK]

Hint: Pointers traverse each list once plus switch [OK]

Common Mistakes:

• Confusing nested loops with two-pointer approach
• Counting intersection length separately
• Misreading max(m,n) as multiplication

3. What is the time complexity of the optimal min-heap based algorithm for merging k sorted linked lists with a total of N nodes?

medium

A. O(N k) because each node is compared with nodes from all k lists.

B. O(N log N) because all nodes are pushed and popped from the heap.

C. O(kN) because each list is merged sequentially with all others.

D. O(N log k) because each of the N nodes is pushed and popped from a heap of size at most k.

Solution

1. Step 1: Identify heap operations per node

   Each node is pushed and popped exactly once from a heap of size ≤ k.

2. Step 2: Calculate complexity

   Heap push/pop cost is O(log k), total O(N log k) for N nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap size depends on k, not N, so O(N log k) [OK]

Hint: Heap size is k, not N, so complexity is O(N log k) [OK]

Common Mistakes:

• Confusing N and k in log factor
• Assuming heap size grows with N
• Thinking sequential merges are optimal

4. Suppose the problem is modified so that if the number of nodes remaining is less than k, you must reverse them as well (i.e., reverse all nodes in the last group regardless of size). Which modification to the optimal iterative approach correctly implements this?

hard

A. Use the original approach but after the main loop, reverse the remaining nodes by calling reverseLinkedList on group_prev.next with the remaining count.

B. Remove the check for group size before reversal and always reverse k nodes; for the last group, reverse whatever nodes remain.

C. Modify the inner while loop to count nodes until the end, then reverse the last group if count < k after the loop ends.

D. Keep the check for k nodes but add a separate recursive call to reverse the last partial group after the main loop.

Solution

1. Step 1: Identify how to handle the last partial group

   The original loop breaks if fewer than k nodes remain, so the last partial group is untouched.

2. Step 2: Reverse the last partial group after the main loop

   After the loop, call reverseLinkedList on group_prev.next with the remaining node count to reverse the last group.

3. Step 3: Why other options fail

   Removing the check causes incorrect reversal attempts; recursive calls add unnecessary complexity; modifying inner loop breaks group boundaries.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Post-loop reversal of leftover nodes correctly handles last partial group [OK]

Hint: Reverse leftover nodes after main loop to handle partial group [OK]

Common Mistakes:

• Removing group size check causes invalid reversals
• Trying to reverse partial group inside main loop breaks logic

5. Suppose the problem is modified so that the linked list is circular (the last node points back to the head). Which of the following modifications to the recursive swapPairs function correctly handles swapping nodes in pairs without causing infinite recursion or losing nodes?

hard

A. Modify the base case to stop recursion when the next node is the head, breaking the cycle.

B. Add a visited set to track nodes and stop recursion when a node repeats.

C. Use the same recursive approach without changes; it naturally terminates on circular lists.

D. Convert the circular list to a linear list by breaking the cycle before swapping.

Solution

1. Step 1: Understand circular list implications

   In a circular list, naive recursion never reaches a null node, causing infinite recursion.

2. Step 2: Modify base case to detect cycle

   Stopping recursion when next node is the head prevents infinite loops and preserves all nodes.

3. Step 3: Compare alternatives

   Using a visited set adds overhead; breaking cycle beforehand changes problem constraints; naive recursion fails.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Base case adjusted for cycle detection prevents infinite recursion [OK]

Hint: Detect cycle in base case to stop recursion [OK]

Common Mistakes:

• Ignoring cycle causes infinite recursion
• Trying naive recursion without cycle check