Solution: Swapping Nodes in a Linked List

Statement

Given the linked list and an integer, k, return the head of the linked list after swapping the values of the $k^{th}$ node from the beginning and the $k^{th}$ node from the end of the linked list.

Note: We’ll number the nodes of the linked list starting from $1$ to $n$.

Constraints:

• The linked list will have n number of nodes.
• $1 \leq$ k $\leq$ n $\leq 500$
• $-5000 \leq$ Node.value $\leq 5000$

Pattern: In-Place Manipulation of a Linked List

We need to find the $k^{th}$ node from the start of the linked list and the $k^{th}$ node from the end of the linked list. We find the two nodes in the linked list using the in-place manipulation method. We use two pointers to traverse the linked list to find the $k^{th}$ node from the start and the $k^{th}$ node from the end of the linked list.

Once we’ve found these nodes, we swap their values without changing their positions.

Solution

There are multiple approaches to solving this problem: the three-pass, two-pass, and one-pass approaches. An efficient approach using a one-pass solution enables the swapping of $k^{th}$ node from both ends of a linked list without determining the length of the list. The method involves advancing two pointers, curr and end, through the list, maintaining a gap of $k$ nodes between them. Initially, both pointers start from the head, with curr moving $k$ steps ahead. When the curr pointer reaches the $k^{th}$ node, the end pointer starts moving from the head, while we use another pointer, front, to store the current position of curr. It continues the traversal by moving both curr and end pointers one step ahead until the curr reaches the end of the list. This ensures that the end pointer points the $k^{th}$ node from the end of the list upon completing the traversal. The final step involves swapping the nodes pointed by the front and end pointers, effectively swapping the positions of the $k^{th}$ nodes from both ends.

Now, let’s look at the different approaches to solving the problem.

The three-pass approach:

Let’s use two pointers, front and end, to help traverse a linked list and find the $k^{th}$ node at the start and end of the linked list:

• First pass: To find the $k^{th}$ node at the start of the linked list, we traverse the linked list from the head to the $k^{th}$ node using the front pointer.