Nth node from the end of a Linked List

To access nodes in a singly linked list we need to sequentially traverse the list. Getting nth node from the end would mean – going to the end and start traversing back. But how do we traverse back ?

We can’t and we don’t need to. There are better ways to do this.

Algorithm
Maintain two pointers – reference pointer and main pointer. Initialize both reference and main pointers to head. First move reference pointer to n nodes from head. Now move both pointers one by one until reference pointer reaches end. Now main pointer will point to nth node from the end. Return main pointer.

Time Complexity: O(n)
Space Complexity: O(1)