Remove the kth node from the end of a singly linked list
A podcast app keeps the episodes a user has queued as a singly linked list. The “Remove” buttons in the queue’s footer are labelled by distance from the end (“last”, “2nd to last”, …), because that is what the user sees at the bottom of the screen. The app needs to unlink that episode and hand it back, so it can be offered in an “Undo” toast.
Implement removeFromEnd(head, k). It removes the k-th node counted from the end of the list (k = 1 is the last node) and returns the new head together with the removed node.
removeFromEnd(head, k) // => { head, removed }
{ value, next }. next is the following node, or null on the last node.head is the first node, or null for an empty list.value can be anything, including falsy values such as 0, '' and null.head: the first node of the list after the removal (null if the list is now empty).removed: the node that was unlinked, with its next set to null.value.k is not an integer from 1 to the length of the list, change nothing and return { head, removed: null } with the original head.// intro -> news -> tech -> sports -> outro
const { head, removed } = removeFromEnd(list, 2);
// head: intro -> news -> tech -> outro (the same intro node)
// removed: sports, with removed.next === null
removeFromEnd(onlyOne, 1); // => { head: null, removed: onlyOne }
removeFromEnd(threeLong, 3); // removes the first node; head is the old second node
removeFromEnd(threeLong, 4); // => { head: threeLong, removed: null } (unchanged)
removeFromEnd(null, 1); // => { head: null, removed: null }
Can you do it in a single pass over the list, without first counting its length?