Katkat
Back

Swap kth-from-end node with head

AmplitudeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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 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.