Daily bit(e) of C++ | Removing n-th element from the end of a singly-linked list
Daily bit(e) of C++ #105, Common interview problem: Removing n-th element from the end of a singly-linked list
Today we will look at a common C++ interview problem: Removing the n-th element from the back of a singly-linked list.
Given a singly-linked list, remove the n-th element from the end of the list.
You should do this in a single pass and only with constant additional memory.
The above illustration is for n==2, i.e. for input {1,2,3,4,5} and n==2, the result is {1,2,3,5}.
Before you continue reading, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/bMdMnxbbn.
Solution
The tricky part of this problem is solving it in a single pass and with constant additional memory.
With O(n*n), we could repeatedly scan n elements ahead. However, if you think about it, that is very wasteful. If we know the previous pair of elements that are n distance from each other, we can get to the next pair by simply advancing both.
That already gives us the solution. We will scan for the first pair and then advance the pair of iterators repeatedly until we find a pair where the second element is at the end of the list.
