643. Swapping Nodes in a Linked List
You receive the head of a singly linked list and an integer k (1-indexed). Locate the k-th node counting from the front and the k-th node counting from the back, exchange their values, and return the head of the list.
Only the stored values trade places — the links between nodes stay exactly as they are. If the list has n nodes, the k-th node from the back is the same node as the (n − k + 1)-th from the front; when those two coincide, the list is unchanged.
Can you find both nodes in a single pass?
Example 1:
Input: head = [1, 2, 3, 4, 5], k = 2
Output: [1, 4, 3, 2, 5]
Explanation: The 2nd node from the front holds 2 and the 2nd node from the back holds 4. Exchanging the two values gives 1 → 4 → 3 → 2 → 5.
Example 2:
Input: head = [7, 9, 6, 6, 7, 8, 3, 0, 9, 5], k = 5
Output: [7, 9, 6, 6, 8, 7, 3, 0, 9, 5]
Explanation: The list has 10 nodes, so the 5th from the front (value 7) and the 5th from the back (value 8) trade values.
Constraints:
- 1 ≤ n ≤ 10⁵, where n is the number of nodes in the list
- -100 ≤ Node.val ≤ 100
- 1 ≤ k ≤ n
Hints:
If the list has n nodes, the k-th node from the back is the (n − k + 1)-th from the front. One pass to count n makes both targets easy to reach.
To do it in one pass, advance a lead pointer k − 1 steps to land on the k-th node, then start a trailing pointer at the head and move both together. When the lead pointer stands on the last node, the trailing pointer stands on the k-th node from the back.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [1, 2, 3, 4, 5], k = 2
Expected output: [1, 4, 3, 2, 5]