TWO POINTERS A FIXED GAP APART. RIGHT JUMPS N PLUS ONE NODES AHEAD, THEN BOTH WALK IN STEP UNTIL RIGHT RUNS OFF THE END. NOW LEFT SITS JUST BEFORE THE TARGET, SO ITS NEXT REACHES PAST IT. A DUMMY BEFORE THE HEAD MAKES REMOVING THE FIRST NODE THE SAME AS ANY OTHER.
RIGHT GETS AN N PLUS ONE NODE HEAD START. AFTER THAT BOTH POINTERS MOVE TOGETHER, SO THE GAP NEVER CHANGES. WHEN RIGHT REACHES THE END, LEFT IS EXACTLY ONE NODE BEFORE THE ONE TO REMOVE.
BLUE LEFT TRAILS, GREEN RIGHT LEADS BY THE GAP. WATCH RIGHT RUN OFF THE END, THEN THE RED TILE IS THE NODE LEFT NEXT ARCS OVER TO REMOVE.
1def removeNthFromEnd(head, n):2 dummy = ListNode(0, head)3 left = right = dummy4 for _ in range(n + 1):5 right = right.next6 while right:7 right = right.next8 left = left.next9 left.next = left.next.next10 return dummy.next
ONE PASS. RIGHT WALKS TO THE END, LEFT FOLLOWS N PLUS ONE BEHIND.
JUST TWO POINTERS AND A DUMMY NODE.