Runner index trick
I used this trick for this hackerrank puzzle where you want to have a specific element counted from the tail of a singly linked list. We traverse this linked list sequentially from the head of the head of the linked list, which makes counting "backwards" a little less trivial.
One particular trick is to keep track of two pointers: we have a normal pointer for indicating the current place in the linked list, and a "runner" pointer that we advance k steps if we want to get the kth element from the tail. We can now increment both pointers one at a time. When the runner pointer (which is k steps ahead) reaches the end of the linked list, we know that the "current" pointer is at the kth element counted from the back. This is pretty good, because we know we can always find a solution in O(n) with constant space complexity, because we only store two additional integers.
In arrays and such, this whole problem never arises because then we can simply use negative indexing arr[-k], since we have random access to the last element.
Example code from my solution:
def getNode(head, positionFromTail):
# Use a runner pointer, k-steps ahead
# When it reaches the end, the *current* pointer is at the correct element.
pointer = head
runner = head
for _ in range(positionFromTail):
runner = runner.next
# Increment one step at a time
while runner.next:
pointer = pointer.next
runner = runner.next
return pointer.data