Find K’th node from the end in a linked list

Given a linked list and a positive integer K, find K’th node from the end in a linked list.

Simple solution would be to calculate number of nodes n in the linked list first. Then, k’th node from the end will be (n-k+1)th node from the beginning.

C

Output:

K’th node from the end is 3

Java

Output:

K’th node from the end is 3

Above solution does two traversal of the linked list. We can solve this problem in one traversal only. The idea is start from the head node and move a pointer K nodes ahead in the given list. Then, we take another pointer starting from head node and run both pointers in parallel till first pointer reaches end of the list. Now, the second pointer will point to K’th node from the end.

C

Output:

K’th node from the end is 3

Java

Output:

K’th node from the end is 3

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

Recursive solution –

This is one of those nice recursive problems where the recursive solution code is much cleaner than the iterative code. You probably wouldn’t want to use the recursive version for production code however, because it will use stack space which is proportional to the length of the lists.

C

Output:

K’th node from the end is 3

Java

Output:

K’th node from the end is 3