Remove Nth Node From End of List
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Remove the n-th node counting from the end of a linked list, in one pass.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Counting the length first needs two passes. Can a gap between two pointers replace the count?
- Hint 2Stop the back pointer one node BEFORE the one to delete.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Two friends walk in single file, kept exactly n steps apart by a rope. The front friend reaches the end of the road. Because the rope never changed, the friend behind is standing exactly n steps from the end. You never had to count the road length first.
- The obvious way
Count the list length, then walk length - n steps: two passes.
- The key insight
Put a dummy node before the head (so deleting the first node is no special case). Send the front pointer n steps ahead. Then move both pointers together until the front one is on the last node. The back pointer is now just before the node to remove, so skip over it.
- The algorithm
- Add a dummy node in front; both pointers start at the dummy.
- Move the front pointer n steps ahead.
- Move both together until the front pointer is on the last node.
- The back pointer is just before the target: set back.next = back.next.next. Return dummy.next.
Watch it run
Examplelist = 1 -> 2 -> 3 -> 4 -> 5, n = 2
Send the front pointer 2 steps ahead: it stands on 2. The back pointer stays at the dummy before 1.
gap = 2
Where people slip
- The dummy node makes deleting the very first node work with the same code.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
# ListNode is provided
def remove_nth_from_end(head, n):
dummy = ListNode(0, head) # so removing the head is not a special case
front = back = dummy
for _ in range(n):
front = front.next # open a gap of n steps
while front.next: # walk until front is on the last node
front = front.next
back = back.next
back.next = back.next.next # skip the target
return dummy.nextNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.