Hi, here's your problem today. This problem was recently asked by AirBNB:

You are given a singly linked list and an integer k. Return the linked list, removing the k-th last element from the list. Try to do it in a single pass and using constant space.

Note: A similar question was asked to me by Amazon, but it was to find the element, not remove it.

Idea behind the solution

We just need to iterate throught the whole list. We need to remove the k-th last element, therefore, after iterating k times we can set the nodeToRemove as being the head of the list. If we are not in the end of the list, we can then set nodeToRemove = nodeToRemove.next, in other words, we just need to remember the element that is k positions behind from the current element in the iteration.

Considering we don't have access to the previous element, we need to keep tracking the element that is k+1 elements behind also, so we can unlink the k element.

The code runs in O(n) (once per each element in the list) and needs O(1) space.

Please check the Solution.java snippet for the solution.

This solution originally posted at: Github by @Murillo2380