Swap Nodes in Pairs

▶

Steps

setup

Setup initial linked list

Initialize the linked list with nodes 1 → 2 → 3 → 4 and set 'head' pointer to node 1.

💡 This sets the starting point for the algorithm to begin swapping pairs.

Line:

n4 = ListNode(4)
n3 = ListNode(3, n4)
n2 = ListNode(2, n3)
n1 = ListNode(1, n2)

💡 The linked list is ready for processing from the head node.

traverse

Enter helper function with node = 1

Call helper(node) with node pointing to the first node (value 1).

💡 This starts the recursive process to swap pairs beginning at the head.

Line:

def helper(node):
    if not node or not node.next:
        return node
    first = node

💡 The base case is not met, so swapping will occur for this pair.

traverse

Identify second node to swap

Set 'second' pointer to node.next, which is node with value 2.

💡 We need both nodes to swap their positions.

Line:

second = node.next

💡 The pair to swap is nodes 1 and 2.

traverse

Recursive call on remainder after second node

Call helper on second.next (node with value 3) to swap subsequent pairs.

💡 This recursive call will process the rest of the list beyond the current pair.

Line:

first.next = helper(second.next)

💡 The algorithm defers swapping the rest of the list until this recursive call returns.

traverse

Helper call with node = 3 (second pair)

Inside recursive call, node points to 3. Check base case for node 3 and node 4.

💡 We are now processing the second pair to swap.

Line:

if not node or not node.next:
    return node
first = node

💡 The algorithm will swap nodes 3 and 4 similarly to the first pair.

traverse

Identify second node in second pair

Set 'second' pointer to node.next, which is node with value 4.

💡 We need both nodes 3 and 4 to swap.

Line:

second = node.next

💡 The pair to swap is nodes 3 and 4.

traverse

Recursive call on remainder after second node in second pair

Call helper on second.next which is null, reaching base case.

💡 No more nodes to swap after node 4, recursion will return null.

Line:

first.next = helper(second.next)

💡 This ends the recursion chain for the last pair.

insert

Swap nodes 3 and 4

Set first.next to null (returned from recursion), then second.next to first, completing swap.

💡 Pointer updates here swap the two nodes in place.

Line:

first.next = helper(second.next)
second.next = first

💡 Swapping is done by reversing the pointers between first and second nodes.

traverse

Return swapped pair head (node 4) to previous call

Return node 4 as new head of swapped sublist to previous recursive call.

💡 This allows the previous call to link the swapped pairs together.

Line:

return second

💡 The recursion returns the new head after swapping pairs.

insert

Link first pair to swapped remainder

Set first.next (node 1) to returned node 4, linking first swapped pair to second.

💡 This connects the two swapped pairs into a single list.

Line:

first.next = helper(second.next)

💡 Linking swapped pairs maintains list continuity.

insert

Complete swap of first pair

Set second.next to first, completing swap of nodes 1 and 2.

💡 This reverses the link between the first two nodes.

Line:

second.next = first

💡 Swapping is done by reversing the pointers between first and second nodes.

traverse

Return new head (node 2) of fully swapped list

Return node 2 as the new head of the entire swapped linked list.

💡 This final return gives the caller the head of the swapped list.

Line:

return second

💡 The swapped list head is the second node of the original list.

traverse

Traverse and print final swapped list

Traverse the swapped list starting at node 2 and print values in order: 2 → 1 → 4 → 3.

💡 This confirms the final output matches expected swapped pairs.

Line:

curr = new_head
while curr:
    print(curr.val, end=' ')
    curr = curr.next

💡 Traversal shows the list is correctly swapped in pairs.

traverse

Advance pointer to next node (1)

Move 'curr' pointer from node 2 to node 1 to continue printing.

💡 Stepwise traversal helps verify the entire list.

Line:

curr = curr.next

💡 Each node is visited in order to confirm list structure.

traverse

Advance pointer to next node (4)

Move 'curr' pointer from node 1 to node 4 to continue printing.

💡 Continuing traversal to confirm all nodes.

Line:

curr = curr.next

💡 Traversal visits nodes in swapped order.

traverse

Advance pointer to next node (3)

Move 'curr' pointer from node 4 to node 3 to continue printing.

💡 Final nodes are visited to complete traversal.

Line:

curr = curr.next

💡 Traversal confirms the last node is linked correctly.

traverse

End traversal at null

Move 'curr' pointer from node 3 to null, ending traversal and printing.

💡 Traversal ends when pointer reaches null, confirming list end.

Line:

curr = curr.next

💡 Traversal completed successfully.

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

def swapPairs(head: ListNode) -> ListNode:
    def helper(node):
        # STEP 2
        if not node or not node.next:
            return node
        # STEP 3
        first = node
        # STEP 3
        second = node.next
        # STEP 4
        first.next = helper(second.next)
        # STEP 8
        second.next = first
        # STEP 9 & 12
        return second
    # STEP 1
    return helper(head)

# Driver code
if __name__ == '__main__':
    # STEP 1
    n4 = ListNode(4)
    n3 = ListNode(3, n4)
    n2 = ListNode(2, n3)
    n1 = ListNode(1, n2)
    new_head = swapPairs(n1)
    curr = new_head
    # STEP 13-17
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

📊

Swap Nodes in Pairs - Watch the Algorithm Execute, Step by Step

Watching each pointer update and recursive call helps you understand how nodes are swapped in place without extra memory.

advance

1

→

2

→

3

→

4

compare

1

→

2

→

3

→

4

advance

1

→

2

→

3

→

4

traverse

1

→

2

→

3

→

4

compare

3

→

4

advance

3

→

4

prune

3

→

4

reverse_link

3

→

4

return

3

→

4

connect

1

→

2

→

3

→

4

reverse_link

1

→

2

→

3

→

4

return

1

→

2

→

3

→

4

traverse

2

→

1

→

4

→

3

Result: [2]

advance

2

→

1

→

4

→

3

Result: [2]

advance

2

→

1

→

4

→

3

Result: [2, 1]

advance

2

→

1

→

4

→

3

Result: [2, 1, 4]

advance

2

→

1

→

4

→

3

Result: [2, 1, 4, 3]

Key Takeaways

✓ The algorithm swaps nodes in pairs by recursively processing the list and reversing pointers between pairs.

This insight is hard to see from code alone because recursion and pointer updates happen implicitly; visualization makes it explicit.

✓ Each recursive call handles exactly one pair, linking the swapped pair to the result of the next recursive call.

Understanding this chaining is easier when you see how the recursive calls return swapped sublists that get connected.

✓ The base case stops recursion when fewer than two nodes remain, ensuring no invalid swaps occur.

Visualizing the base case clarifies why the algorithm safely handles lists with odd or even lengths.

Practice

1. You are given a sorted singly linked list and need to remove all duplicate nodes so that each element appears only once. Which approach guarantees an optimal in-place solution with linear time complexity and constant extra space?

easy

A. Use a hash set to track seen values and remove duplicates by reconstructing the list.

B. Use a nested loop to compare each node with all subsequent nodes and remove duplicates.

C. Iterate once through the list, comparing each node with its next node and removing duplicates in-place.

D. Sort the list first, then remove duplicates by scanning through it.

Solution

1. Step 1: Understand the problem constraints

   The list is already sorted, so duplicates appear consecutively, allowing a single pass to remove them efficiently.

2. Step 2: Identify the optimal approach

   Iterating once and comparing each node with its next node lets us remove duplicates in-place with O(n) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with pointer manipulation matches optimal solution [OK]

Hint: Sorted list allows single pass duplicate removal [OK]

Common Mistakes:

• Thinking nested loops are needed despite sorted input

2. You are given a singly linked list and an integer k. The task is to rotate the list to the right by k places. Which of the following approaches guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Repeatedly move the last node to the front k times, each time traversing the list to find the last node.

B. Reverse the entire list, then reverse the first k nodes and the remaining nodes separately.

C. Use a dynamic programming approach to store intermediate rotations and reuse them to build the final rotated list.

D. Calculate the length of the list, connect the tail to the head to form a circular list, then find the new tail using two pointers and break the circle.

Solution

1. Step 1: Understand the problem constraints

   Rotating a linked list by k places requires rearranging nodes efficiently without extra space.

2. Step 2: Identify the optimal approach

   Calculating length and connecting tail to head forms a circular list, then using two pointers to find the new tail and breaking the circle achieves O(n) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal approach uses length calculation and two pointers [OK]

Hint: Optimal rotation uses length + two pointers [OK]

Common Mistakes:

• Using repeated single rotations leads to O(n*k) time
• Misapplying DP or reversal techniques that don't fit linked list rotation

3. Consider the following buggy code snippet for removing the nth node from the end of a linked list. Which line contains the subtle bug that causes incorrect behavior when removing the head node?

medium

A. Line 13: Wrong condition for node removal

B. Line 10: Incorrect base case for recursion

C. Line 5: Missing dummy node initialization

D. Line 15: Returning head instead of dummy.next

Solution

1. Step 1: Identify missing dummy node

   Without a dummy node, removing the head node causes pointer errors or incorrect list head.

2. Step 2: Check recursion call and return

   Recursion is called on head, but no dummy means no safe predecessor to update head pointer.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Dummy node is essential to handle head removal safely [OK]

Hint: Always use dummy node to handle head removal [OK]

Common Mistakes:

• Not using dummy node
• Incorrect recursion base case
• Returning wrong node after removal

4. Suppose the problem is modified so that the linked list is circular (last node points back to head). Which of the following changes is necessary to correctly remove the nth node from the end in one pass?

hard

A. Use the same two-pointer approach without changes; it works as is.

B. First break the circular link to convert it into a linear list, then apply the standard algorithm.

C. Use a hash set to detect the cycle and count nodes before removal.

D. Modify the recursion to detect when the node revisits the head to stop infinite recursion.

Solution

1. Step 1: Understand circular list implications

   In a circular list, traversal never ends naturally, so counting nodes or recursion can loop infinitely.

2. Step 2: Break the cycle

   Temporarily breaking the cycle converts it to a linear list, allowing standard removal algorithms to work correctly.

3. Step 3: Restore circular link if needed

   After removal, reconnect the last node to the new head to restore circularity.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Breaking cycle prevents infinite loops and enables standard logic [OK]

Hint: Circular lists require cycle breaking before linear algorithms [OK]

Common Mistakes:

• Assuming two-pointer works on circular lists
• Using recursion without cycle detection
• Using extra space unnecessarily

5. Suppose you want to reverse a singly linked list that may contain cycles (i.e., some node's next pointer points to a previous node). Which modification to the standard tail-recursive reversal algorithm correctly handles this scenario without infinite recursion?

hard

A. Add a visited set to track nodes already reversed and stop recursion if a node repeats.

B. Use the standard tail-recursive reversal without changes; cycles will be reversed naturally.

C. Convert the list to an array first, then reverse the array and rebuild the list to avoid cycles.

D. Limit recursion depth to a fixed number to prevent infinite loops in cycles.

Solution

1. Step 1: Understand cycle problem

   Standard reversal assumes acyclic list; cycles cause infinite recursion or loops.

2. Step 2: Modify algorithm

   Tracking visited nodes prevents revisiting and infinite recursion by stopping when a node repeats.

3. Step 3: Evaluate other options

   Standard recursion (B) fails on cycles. Converting to array (C) is inefficient and not in-place. Limiting recursion depth (A) is arbitrary and unsafe.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited set detects cycles and prevents infinite recursion [OK]

Hint: Detect cycles with visited set to avoid infinite recursion [OK]

Common Mistakes:

• Assuming input list is always acyclic
• Ignoring cycle detection in recursive reversal