Swapping Nodes in a Linked List
Swapping Nodes in a Linked List is a problem that looks simple on the surface, but is designed to test whether you truly understand how linked lists work. You are given the head of a singly linked list and an integer k. Your task is to swap the values of the kth node from the beginning with the kth node from the end of the list.
It is important to notice that the problem asks you to swap the values, not the nodes themselves. This distinction matters because swapping nodes directly would require carefully re-linking pointers, which is more complex and not required here.
The list is one-indexed. That means the first node is position 1, not position 0. If k is 1, you are swapping the first and last nodes. If k is in the middle, you may end up swapping a node with itself.
Why this problem is not about pointer manipulation
Many candidates overthink this problem and try to rearrange pointers. That often leads to bugs, especially around the head of the list or adjacent nodes.
Since only the values need to be swapped, the problem becomes much simpler. You only need to identify the two target nodes. Once you have them, swapping their values is straightforward.
Interviewers often include this detail deliberately. They want to see whether you can read the problem carefully and avoid unnecessary complexity.
Want to explore more coding problem solutions? Check out the Find the Index of the First Occurrence in a String and Best Time to Buy and Sell Stock with Transaction Fee.
The key challenge: finding the two nodes efficiently
The real challenge is locating the kth node from the start and the kth node from the end.
Finding the kth node from the beginning is easy. You simply move forward k - 1 steps from the head.
Finding the kth node from the end is slightly more interesting. A common mistake is to first count the total number of nodes, then compute the index from the start, and then traverse again. While this works, it requires two full passes.
A more elegant approach uses the two-pointer technique and finds both nodes in a single pass.
How the two-pointer technique works
You start with two pointers, both initially pointing to the head of the list.
First, you move the first pointer forward by k - 1 steps. At this point, this pointer is positioned at the kth node from the beginning. You save a reference to this node.
Next, you keep the first pointer where it is and begin moving both pointers forward together, one step at a time.
When the first pointer reaches the last node, the second pointer will be positioned at the kth node from the end.
This works because the distance between the two pointers remains constant. When one pointer hits the end, the other has exactly the right offset from it.
This technique avoids the need to count nodes explicitly and keeps the logic clean.
Swapping the values
Once you have references to both target nodes, the final step is simple.
You swap the values stored in those two nodes. The structure of the linked list remains unchanged, and no pointers are modified.
If the two nodes happen to be the same node, which can happen when k points to the middle of an odd-length list, the swap has no effect. The algorithm still works without any special handling.
Why this approach is reliable
This solution works for all valid inputs because it relies only on traversal, not on pointer rearrangement.
It handles edge cases naturally, including swapping the first and last nodes, swapping adjacent nodes, and swapping the same node with itself.
Because you never break or reassign links between nodes, there is no risk of losing part of the list or creating cycles.
Performance in simple terms
The list is traversed once, so the time complexity is linear in the number of nodes.
Only a constant number of pointers are used, so space usage is constant.
This makes the solution efficient and suitable for large lists.
Top comments (0)