Saturday, 30 July 2016

How to find the 3rd element from end in linked list in Java

The problem to find the 3rd element from the end in a singly linked list or nth node from the tail is one of the tricky but frequently asked linked list problems in programming job interviews. The challenge here is to solve the problem in just one pass, i.e. you can not traverse the linked list again and you cannot traverse backward because it's a singly linked list. If you have practiced some linked list problems e.g. finding length, inserting elements, or deleting elements then you should be familiar with traversal. Here, we'll use the same algorithm which we have used to find the middle element of linked list in one pass. The algorithm is also known as tortoise and hare algorithm because of the speed of two pointers used by the algorithm to traverse the singly linked list.
Read more »

No comments:

Post a Comment