So, did you try to solve this problem on your own? There is this trick here in the constraints that you cannot solve the problem by using the size property. Otherwise, it would have been a piece of cake, right? So, the solution to this problem is called the Two Pointer Approach and it is not only used in this problem, but it is used in many problems. Let us try to understand the basis of this two pointer approach first in a fun way.
The Idea Behind The Two Pointer Approach:
Let us consider a racing track (500m long). Let us say there are two people. They are you and me. So, my friend, you and I are on a racing track and the race has not started yet. You are already standing at the 200m spot while I am at the starting position i.e. the 0m spot. (Have a look at fig-4)
Now, let us assume that we run at the exact same speed. So, when the race starts, both of us start running and we run at the exact same speed, say 20m/s. So, what do you think? Who is going to be the winner? Of course, it is going to be you (and believe me I am not jealous).
Can you think why you would win if we were running at the exact same speed? It's obvious that you started from the 200m spot and I was at the 0m spot.
What do you think will be the distance between us when you finish the race? Well, it is still going to be 200m because we ran at the same speed. So, the distance between us remained constant throughout the race as we ran with the same speed.
This is the basis for the two pointer approach.
Two Pointer Approach on Linked List:
Ok, now let's get back to our question. We have to find the kth element from the end of the list. We will use the above idea and solve this problem.
- Make two pointers slow and fast and keep them both on the head of the linked list.
- Now, move the fast pointer k steps away from the slow pointer. (see fig-5)
- Now, move the fast pointer and the slow pointer each one step at a time till the fast pointer reaches the tail of the linked list. When the fast pointer reaches the tail, the node at which the slow pointer resides will be our answer. (See fig-6)
Now that we have understood the entire procedure, let us write the code for the same.