Swap kth-from-end node with head
Company: Amplitude
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given the head of a singly linked list and an integer `k`, swap the **k-th node from the end** with the **head node**, using **O(1)** extra memory.
Requirements:
- Perform the swap by changing pointers (swap nodes), not by swapping values.
- Assume `1 <= k <= n` where `n` is the list length.
- If the k-th node from the end is already the head (i.e., `k == n`), return the list unchanged.
Examples (list: `1 -> 2 -> 3 -> 4 -> 5 -> 6`):
- `k = 1` => `6 -> 2 -> 3 -> 4 -> 5 -> 1`
- `k = 2` => `5 -> 2 -> 3 -> 4 -> 1 -> 6`
- `k = 5` => `2 -> 1 -> 3 -> 4 -> 5 -> 6`
Return the new head of the linked list.
Quick Answer: This question evaluates a candidate's understanding of singly linked list pointer manipulation, in-place node swapping with O(1) extra memory, and handling of edge cases such as when the k-th node from the end is the head.
Given a singly linked list (represented head-to-tail as an array of node values) and an integer `k`, swap the **k-th node from the end** with the **head node**, then return the resulting list.
The k-th node from the end (1-indexed) sits at 0-based position `n - k`, where `n` is the list length. Conceptually you perform the swap by relinking pointers (swapping nodes, not copying values); on the array representation this is exactly swapping the value at index 0 with the value at index `n - k`.
Rules:
- Use O(1) extra memory.
- Assume `1 <= k <= n`.
- If the k-th node from the end is already the head (`k == n`), return the list unchanged.
Example (`[1, 2, 3, 4, 5, 6]`):
- `k = 1` => `[6, 2, 3, 4, 5, 1]`
- `k = 2` => `[5, 2, 3, 4, 1, 6]`
- `k = 5` => `[2, 1, 3, 4, 5, 6]`
Return the new list order from head to tail.
Constraints
- 1 <= k <= n where n is the list length
- 0 <= n (the list may be empty)
- Node values fit in a 32-bit signed integer
- Only O(1) extra memory may be used
Examples
Input: ([1,2,3,4,5,6], 1)
Expected Output: [6, 2, 3, 4, 5, 1]
Explanation: k=1: the last node (6) swaps with the head (1). Result reads 6,2,3,4,5,1.
Input: ([1,2,3,4,5,6], 2)
Expected Output: [5, 2, 3, 4, 1, 6]
Explanation: k=2: the 2nd-from-end node (5, index n-k=4) swaps with the head (1).
Hints
- The k-th node from the end of an n-element list (1-indexed) is at 0-based index n - k. Use the two-pointer technique to reach it in one pass without storing the list.
- Swapping the head with the k-th-from-end node by relinking pointers reorders the chain so that, read head-to-tail, those two nodes trade positions.
- Watch the no-op case: when k == n, n - k == 0, so the target node IS the head and you must return the list unchanged.