Remove Duplicates from Sorted List

▶

Steps

setup

Initialize current pointer to head

Set the 'current' pointer to the head of the list to start traversal from the first node.

💡 Starting at the head is necessary to examine all nodes sequentially.

Line:

current = head

💡 The algorithm begins by examining the first node to check for duplicates ahead.

compare

Check if current and current.next exist

Verify that 'current' and 'current.next' are not null to ensure there is a next node to compare.

💡 This check prevents null pointer errors and ends traversal when the list ends.

Line:

while current and current.next:

💡 Traversal continues as there is a next node to compare with.

compare

Compare current.val and current.next.val

Compare the value of the current node (1) with the value of the next node (1) to detect a duplicate.

💡 Duplicates are identified by equal adjacent values in a sorted list.

Line:

if current.val == current.next.val:

💡 Duplicate nodes have the same value and should be removed by skipping the next node.

delete

Skip the duplicate node by adjusting current.next

Remove the duplicate node by setting current.next to current.next.next, effectively skipping the duplicate node.

💡 Adjusting pointers removes duplicates without extra memory allocation.

Line:

current.next = current.next.next

💡 Pointer adjustment removes the duplicate node from the linked list.

compare

Check if current and current.next exist again

Check again if current and current.next exist to continue traversal after removing a duplicate.

💡 The loop condition is re-evaluated after pointer changes.

Line:

while current and current.next:

💡 Traversal continues to check for further duplicates.

compare

Compare current.val and current.next.val again

Compare the current node's value (1) with the next node's value (2) to check for duplicates.

💡 If values differ, no duplicate removal is needed.

Line:

if current.val == current.next.val:

💡 No duplicate means we move the current pointer forward.

advance

Move current pointer forward

Advance the current pointer to the next node since no duplicate was found.

💡 Moving forward allows the algorithm to check the next pair of nodes.

Line:

current = current.next

💡 Pointer advancement is key to traversing the entire list.

compare

Check if current and current.next exist at last node

Check if current and current.next exist to determine if traversal continues.

💡 At the last node, current.next is null, so traversal ends.

Line:

while current and current.next:

💡 Traversal ends when there are no more nodes to compare.

reconstruct

Return the head of the modified list

Return the head pointer which now points to the list with duplicates removed.

💡 Returning head allows access to the cleaned linked list.

Line:

return head

💡 The list starting at head is now free of duplicates.

reconstruct

Final linked list after duplicate removal

The final linked list contains nodes with values 1 and 2, with duplicates removed.

💡 This final state confirms the algorithm's correctness visually.

💡 The duplicate '1' node is removed, leaving a sorted list without duplicates.

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

def deleteDuplicates(head):
    current = head  # STEP 1
    while current and current.next:  # STEP 2,5,8
        if current.val == current.next.val:  # STEP 3,6
            current.next = current.next.next  # STEP 4
        else:
            current = current.next  # STEP 7
    return head  # STEP 9

# Driver code
if __name__ == '__main__':
    head = ListNode(1, ListNode(1, ListNode(2)))
    new_head = deleteDuplicates(head)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

📊

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

Watching each pointer move and comparison helps you understand how duplicates are detected and removed without extra space.

advance

1

→

1

→

2

compare

1

→

1

→

2

compare

1

→

1

→

2

detach

1

→

1

→

2

compare

1

→

1

→

2

compare

1

→

1

→

2

advance

1

→

1

→

2

compare

1

→

1

→

2

reconstruct

1

→

1

→

2

Result: [1, 2]

reconstruct

1

→

2

Result: [1, 2]

Key Takeaways

✓ The algorithm removes duplicates by adjusting pointers in-place without extra memory.

This insight is hard to see from code alone because pointer manipulation is implicit; visualization shows exactly which nodes are skipped.

✓ Traversal stops when the current node or its next node is null, ensuring safe pointer access.

Understanding loop termination conditions is easier when you see the pointers and nodes involved.

✓ When adjacent nodes have different values, the current pointer advances, preserving unique nodes.

Visualizing pointer movement clarifies how the algorithm progresses through the list.

Practice

1. You are given k sorted linked lists and need to merge them into one sorted linked list efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Merge all lists into one array, then sort the array and rebuild the linked list.

B. Use dynamic programming to store intermediate merged results and avoid repeated merges.

C. Use a min-heap (priority queue) to repeatedly extract the smallest node among the heads of the lists.

D. Merge the lists one by one sequentially, merging two lists at a time from left to right.

Solution

1. Step 1: Understand problem constraints

   We have k sorted linked lists and want to merge them efficiently.

2. Step 2: Compare approaches

   Brute force sorting all nodes is O(N log N). Sequential merges cost O(kN). Min-heap approach extracts smallest node in O(log k) time, total O(N log k), which is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Min-heap approach uses priority queue to achieve O(N log k) [OK]

Hint: Min-heap merges k lists in O(N log k) time [OK]

Common Mistakes:

• Thinking sequential merges are optimal
• Assuming sorting all nodes is best
• Confusing DP with merge approach

2. Consider the following code snippet implementing the optimal iterative approach to reverse nodes in k-groups. Given the linked list 1 -> 2 -> 3 -> 4 and k = 2, what is the value of group_prev.next.val after the first reversal group is processed inside the while loop?

easy

A. 1

B. 4

C. 2

D. 3

Solution

1. Step 1: Trace the first group reversal with k=2 on list 1 -> 2 -> 3 -> 4

   The first group is nodes with values 1 and 2. Reversing them results in 2 -> 1.

2. Step 2: Identify group_prev.next after reversal

   After reversal, group_prev.next points to the new head of the reversed group, which is node with value 2.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   First group's head after reversal is 2 [OK]

Hint: After reversal, group_prev.next points to new group's head [OK]

Common Mistakes:

• Assuming group_prev.next still points to original head (1)
• Confusing tail and head pointers after reversal

3. Given the following recursive code for swapping nodes in pairs, what is the output when the input list is 1 -> 2 -> 3 -> null?

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

def swapPairs(head: ListNode) -> ListNode:
    def helper(node):
        if not node or not node.next:
            return node
        first = node
        second = node.next
        first.next = helper(second.next)
        second.next = first
        return second
    return helper(head)

# Input list: 1 -> 2 -> 3 -> null

What is the printed output after swapping pairs?

easy

A. 2 3 1

B. 1 3 2

C. 2 1 3

D. 3 2 1

Solution

1. Step 1: Trace helper on node with val=1

   First = 1, Second = 2; recursively call helper on node with val=3.

2. Step 2: Trace helper on node with val=3

   Node 3 has no next, so return node 3 as is.

3. Step 3: Complete first call

   Set first.next = node 3, second.next = first (1), return second (2). Resulting list: 2 -> 1 -> 3.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Output matches expected swapped pairs [OK]

Hint: Recursive swaps pairs, last odd node remains [OK]

Common Mistakes:

• Swapping values instead of nodes
• Misplacing last node in odd-length list

4. Consider the following buggy code snippet for adding two linked lists representing numbers in forward order. Which line contains the subtle bug that causes incorrect results when the sum produces a carry beyond the most significant digit?

medium

A. Line 2: Calculating length of l1

B. Line 7: Calling addListsHelper recursively

C. Line 4: Padding the shorter list

D. Line 9: Returning head without handling carry

Solution

1. Step 1: Identify carry handling after addition

   The code calls addListsHelper which returns carry, but the carry is ignored before returning the head.

2. Step 2: Understand impact of missing carry

   If carry is non-zero, the result should prepend a new node with carry value; missing this causes incorrect sum for cases like 999 + 1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Carry ignored after addition leads to wrong output length [OK]

Hint: Always check carry after recursive addition [OK]

Common Mistakes:

• Ignoring carry after final addition
• Incorrect padding causing misalignment
• Modifying input lists unexpectedly

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