Swapping Nodes in a Linked List

Explanation & Solution

Description

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

Input:head = [1,2,3,4,5], k = 2

Output:[1,4,3,2,5]

Explanation: The 2nd node from the beginning (value 2) and the 2nd node from the end (value 4) are swapped.

Constraints

The number of nodes in the list is n
1 <= k <= n <= 10⁵
0 <= Node.val <= 100

Approach

In-Place Manipulation of a Linked List pattern

1. Find the k-th Node from the Beginning

Start at head and advance k - 1 steps to reach first.
This is the k-th node from the start.

2. Find the k-th Node from the End

Use two pointers: runner starts at first, and second starts at head.
Advance both runner and second together until runner reaches the last node.
Since runner started k nodes in, when it reaches the end, second is k nodes from the end.

3. Swap the Values

Swap first.val and second.val.
Since we only need to swap values (not nodes), this is a simple temp-variable swap.

4. Return the Result

Traverse the list and collect values into an array.

🧠 Key Insight

The two-pointer gap technique elegantly finds the k-th node from the end in a single pass without knowing the list length.

Time

O(n)one traversal to find both nodes.

Space

O(1)only pointer variables are used.

Visualization

Input:

Linked List Traversal

—

Press play to start traversal

Slow (S)Fast (F)Both

4 steps

Solution Code

Reorder List

Partition List