Swapping Nodes in a Linked List

Swapping Nodes in a Linked List

What is this problem about?

The Swapping Nodes in a Linked List interview question asks you to swap the values of the k-th node from the beginning and the k-th node from the end of a linked list. For example, if the list is 1 -> 2 -> 3 -> 4 -> 5 and k = 2, the 2nd node from the beginning is 2 and the 2nd node from the end is 4. After swapping their values, the list becomes 1 -> 4 -> 3 -> 2 -> 5.

Why is this asked in interviews?

This "Medium" problem is frequently asked by Microsoft, Amazon, and Google. It tests your proficiency with linked list traversal and the two-pointer technique (specifically the "slow and fast pointer" or "fixed distance pointer" strategy). It's a great way to see if a candidate can find the k-th node from the end in a single pass without first calculating the total length of the list.

Algorithmic pattern used

The primary pattern is the Two Pointers or Fast/Slow Pointer interview pattern.

1. Find the k-th node from the start by moving a pointer first k-1 times from the head.
2. To find the k-th node from the end, use another pointer second. Start second at the head and a temporary pointer temp at first. Move both temp and second until temp reaches the last node. second will now be at the k-th node from the end.
3. Swap the values of first and second.

Example explanation

List: [10, 20, 30, 40, 50, 60], k = 2.

1. first moves to the 2nd node: 20.
2. To find the 2nd from the end:
   • temp starts at first (20), second starts at head (10).
   • Move temp and second together:
     • temp -> 30, second -> 20
     • temp -> 40, second -> 30
     • temp -> 50, second -> 40
     • temp -> 60 (tail), second -> 50.
3. second is at 50. Swap values of first (20) and second (50). Result: [10, 50, 30, 40, 20, 60].

Common mistakes candidates make

A common error is confusing 1-based and 0-based indexing for k. Another mistake is thinking you must swap the nodes themselves (which involves updating four pointers) when the problem only asks to swap the values. While swapping nodes is more challenging and might be asked as a follow-up, swapping values is the standard requirement.

Interview preparation tip

When preparing for the Swapping Nodes in a Linked List coding problem, practice finding the "k-th from end" in one pass. It’s a foundational linked list skill. Also, remember that while swapping values is easier, in a real-world scenario with large objects, swapping the pointers (nodes) is often more efficient than copying the data.