Dec-15-2020, 11:30 PM
If you wanted to assume the linked list was "big" (so you didn't want to copy the data), and you want to do only one pass, then you have to keep track of the last n+1 nodes. Could toss them onto a queue or a deque of size n+1.
When you reach the end, the head of the queue either has the previous node (which is the one that has to be modified), or your list is shorter and you might have a special case or two to handle.
When you reach the end, the head of the queue either has the previous node (which is the one that has to be modified), or your list is shorter and you might have a special case or two to handle.