Find the K'th last Node in Linked List

Given a linked list and an Integer K, your task is to find the Kth last node of the linked list.

Input : 1->2->3->4->Null and K = 2

Output : 3

1. Native approach

To solve this problem first we have to find a length of the linked list and then subtract K from it so you'll get K'th node from the front of the list, and then traverse again up to K.

but wait! is this approach is efficient of course not, it takes O(N+(N-K)).

2. Two pointer approach

First, take two pointers fast and slow, and move the fast pointer forward up to the first K node.

Then again move forward (fast pointer) with a slow pointer so, when the fast pointer reaches to null, slow pointer reaches to Kth node from last.

Let's see this in action (Implementation in Java).

Thank you so much for reading this article, if you like this question please share this with your friends who love programming. And if you have questions or feedback please drop a comment.

To solve more problems on Array and String please check out these articles "Top 10 Array Interview Questions" and "Top 10 String Interview Questions".

All the Best!