Swapping Nodes in a Linked List
Problem
Given the head of a linked list and an integer k, swap the values of the kth node from the front and the kth node from the end.
head = [1,2,3,4,5], k = 2[1,4,3,2,5]def swap_nodes(head, k):
a = head
for _ in range(k - 1):
a = a.next
front = a
b = head
while a.next:
a = a.next; b = b.next
front.val, b.val = b.val, front.val
return headfunction swapNodes(head, k) {
let a = head;
for (let i = 1; i < k; i++) a = a.next;
const front = a;
let b = head;
while (a.next) { a = a.next; b = b.next; }
[front.val, b.val] = [b.val, front.val];
return head;
}class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode a = head;
for (int i = 1; i < k; i++) a = a.next;
ListNode front = a, b = head;
while (a.next != null) { a = a.next; b = b.next; }
int t = front.val; front.val = b.val; b.val = t;
return head;
}
}ListNode* swapNodes(ListNode* head, int k) {
ListNode* a = head;
for (int i = 1; i < k; i++) a = a->next;
ListNode* front = a;
ListNode* b = head;
while (a->next) { a = a->next; b = b->next; }
swap(front->val, b->val);
return head;
}Explanation
We need the kth node from the front and the kth node from the end, then swap their values. The neat part is finding the end node in a single pass without first measuring the list's length.
We move a pointer a forward k - 1 steps so it lands on the front-kth node. We save that as front.
Now the two-pointer gap trick: we start a second pointer b at the head and walk a and b together until a reaches the last node. Because a started k - 1 nodes ahead, when a hits the end, b is exactly k nodes from the end.
Finally we swap the values of front and b and return the unchanged head. Only values move, so no pointer surgery is needed.
Example: [1,2,3,4,5], k=2. a steps to index 1 (value 2), that's front. Then a and b walk together until a reaches 5; b lands on value 4. Swapping gives [1,4,3,2,5].