Swapping Nodes in a Linked List
Medium · Linked Lists · Linked List · Two Pointers
Problem
You are given the head of a linked list and an integer k. Swap the values of the k-th node from the start and the k-th node from the end, both counted from 1, and return the head of the list.
When both positions name the same node (the middle of an odd-length list), the list stays as it is.
Examples
Input: head = [7,3,9,1,4], k = 2 Output: [7,1,9,3,4]
The 2nd node from the start holds 3 and the 2nd from the end holds 1; they trade values.
Input: head = [8,6], k = 1 Output: [6,8]
The first and last nodes swap values.
Input: head = [1,2,3,4,5], k = 3 Output: [1,2,3,4,5]
The 3rd node from either end is the same node, so nothing changes.
Constraints
- The list has n nodes, 1 <= k <= n <= 10^5
- 0 <= Node.val <= 100
Approaches
- Baseline: store the nodes in an array — time O(n), space O(n)
Follow-up
If the nodes had to be swapped by relinking rather than by value (say each node carries a large payload), you would also track the node before each one and handle the cases where the two nodes are adjacent or the same. A dummy node in front of the head removes the special case at the head.
Related problems
Start free on Cariara · Coding problems · System design studio
