The goal is to find Nth last node in a given linked list. This can be done by using an imaginary stick.
A stick can be imagined in code by using left and right pointers.
# Problem: Getting Nth to last node in LinkedList
# Logic: Use a stick with two pointers
def find_nth_node(n, node):
left_pointer = node
right_pointer = node
for i in range(n):
if right_pointer:
right_pointer = right_pointer.next
# right_pointer is now n nodes ahead
while right_pointer:
left_pointer = left_pointer.next
right_pointer = right_pointer.next
return left_pointer
# Testing the result
a = Node(1) #0 -- default right_pointer value
b = Node(2) #1 -- first iteration
c = Node(3) #2 -- second iteration - right_pointer gets here after being n nodes ahead
d = Node(4) #3
e = Node(5) #4
a.next = b
b.next = c
c.next = d
d.next = e
find_nth_node(2, a).value # second last node's val is 4
The first for loop in the code brings our right_pointer in position (n steps ahead of left_pointer), thus creating our imaginary stick.
Once that’s in place, we are ready to find the Nth last node.
The second for loop keeps moving the left_pointer and the right_pointer to the next node as long as the right_pointer points to some node. It stops once it points to Null or None (which is at the end of the Linked List).
The above can be imagined as our stick moving across the given Linked List with left_pointer and right_pointer moving to the right one step (one node) at a time.
Once the second for loop stops, the right_pointer will point to None (the end of the Linked List). Since the length of the stick is N, we can safely say our left_pointer is now pointing at Nth last node.
Therefore printing the value of the node pointed by the left_pointer gives us the value of Nth last node.
In the example given above, the Nth last node (the second last node) is 4.
CS Mumbai 