Swapping Nodes in a Linked List - Video Solutions

Problem Overview: Given the head of a singly linked list and an integer k, swap the values of the kth node from the beginning and the kth node from the end. The list structure must remain intact, so you typically swap node values rather than rearranging node pointers.

Approach 1: Two Pass Technique (O(n) time, O(1) space)

This method first computes the total length of the linked list. Once you know the length n, the node to swap from the end becomes the (n - k + 1)th node from the beginning. Perform one traversal to count nodes, then a second traversal to locate both the kth node and the (n - k + 1)th node. After locating them, swap their values. The logic is simple and easy to reason about during interviews because you separate the tasks: measure the list, then locate the targets. Time complexity is O(n) due to two linear passes, while space complexity stays O(1) since only a few pointers are used.

Approach 2: Single Pass with Two Pointers (O(n) time, O(1) space)

This optimized approach finds both nodes in a single traversal using the two pointers technique. First iterate until you reach the kth node from the start and keep a reference to it. Then start a second pointer from the head while continuing the traversal with the current pointer until the end. When the first pointer reaches the last node, the second pointer will land exactly on the kth node from the end. Swap the values of these two nodes. This technique works because the gap between the pointers remains constant after the kth node is identified. It completes the entire operation in one pass with O(n) time and O(1) space.

Recommended for interviews: The single-pass two pointer method is usually the expected optimal solution. It demonstrates control over pointer movement and efficient traversal of a linked list. The two-pass method is still valuable because it shows a clear understanding of indexing in linked structures and often serves as the stepping stone toward the optimized approach.