How to find the 3rd (kth) Node from end or tail in a linked list in Java

Hello guys, the problem to find the 3rd element from the end in a singly linked list or Kth node from the tail is one of the tricky but frequently asked linked list problems in Programming job interviews. I know you can easily solve this problem by moving from tail to head or in the reverse direction but the main challenge here is to solve the problem in just one pass. That means, you can not traverse the linked list again and you cannot traverse backward because it's a singly linked list. So what do you think? Isn't this problem challenging? Well, I did struggle when I saw this problem very first time but once you understand the logic and some tricks to solve a linked list based problem like Recursion then it would be easy for you, and that's what you will learn in this article.

If you have practiced some linked list problems likefinding the length, inserting elements, or deleting elements then you should be familiar with how to traverse through a linked list. Here, we'll use thetortoise and hare algorithm to solve this problem. This is the same algorithm which we have used tofind the middle element of linked list in one pass.

It's known as tortoise and hare because of the speed of two pointers used by the algorithm to traverse the singly linked list and I am sure you have heard how slow tortoise win the race with a fast rabbit in your childhood.

Anyway, the algorithm uses two pointers, fast and slow. The slow pointer starts when the fast pointer is reached to Nth or Kth node. For example, in order to find the 3rd element from the last, the second pointer should start when the first pointer has reached to the third element.

After that, both pointers will keep moving one step at a time until the first pointer points to null, which signals the end of the linked list. At this time, the second pointer is pointing to the 3rd or Nth node from the last.

Congratulations, you have solved the problem, you can either the print value of a node or return reference to the caller based upon your requirement. Btw, if you are not familiar with the linked list data structure, it's better to first go through a  good data structure and algorithm course like Data Structures and Algorithms: Deep Dive Using Java  to learn more about linked list data structure in Java.

Java Program to find the Nth Node from tail in a linked list

Here is our complete Java program to find the Kth element from the tail in a singly linked list in Java. This program solves this program in one pass which means the linked list is traversed only once.

You can see that we have used just one while loop in the getLastNode(int n) method. This method accepts an integer parameter and can be used to find the nth element from the end in the linked list like to get the 2nd element from the tail, pass 2 and to get the 3rd element from the list, pass 3. Similarly to get the Kth node from the tail, just pass K.

The SinglyLinkedList class represents a singly linked list in Java. It is the same class which we have used earlier linked list articles like writing your own linked list in Java. It is a collection of Node class which represent a node in the linked list. It contains a data part and a reference to the next node. The SinglyLinkedList class also contain a reference to head, the first node of the linked list.

As a programmer, you should know  key data structures and algorithms like what is a linked list data structure, it's pros and cons and when to use linked list like it is good for frequently adding and removing element but not so good for search as it takes O(n) time to find an element inside linked list.

You can read more about the linked list in a good data structure and algorithm course like Algorithms and Data Structures - Part 1 and 2  on Pluralsight, one of the best course to learn data structures and algorithms.

Here is also a visual explanation of finding the 2nd element from the tail in the singly linked list. You can see how both fast and slow pointer navigates and when the fast pointer points to tail how slow pointer points to the nth node from the end.

And if you like books then Introduction to Algorithms is an awesome book to refer. Initially, you may not like this book as it is a little bit difficult to understand because of the topic and style but you must stick with it and refer it now and then to understand the key data structures like the array, linked list, binary trees, hash table, etc.

The Kth Node from the End in a Singly linked list

public class Practice { public static void main(String args[]) { SinglyLinkedList list = new SinglyLinkedList(); list.append("1"); list.append("2"); list.append("3"); list.append("4"); System.out.println("linked list : " + list); System.out.println("The first node from last: " + list.getLastNode(1)); System.out.println("The second node from the end: " + list.getLastNode(2)); System.out.println("The third node from the tail: " + list.getLastNode(3)); } } /** * Java Program to implement linked list data structure * * @author Javin * */ class SinglyLinkedList { static class Node { private Node next; private String data; public Node(String data) { this.data = data; } @Override public String toString() { return data.toString(); } } private Node head; // Head is the first node in linked list /** * checks if linked list is empty * * @return true if linked list is empty i.e. no node */ public boolean isEmpty() { return length() == 0; } /** * appends a node at the tail of this linked list * * @param data */ public void append(String data) { if (head == null) { head = new Node(data); return; } tail().next = new Node(data); } /** * returns the last node or tail of this linked list * * @return last node */ private Node tail() { Node tail = head; // Find last element of linked list known as tail while (tail.next != null) { tail = tail.next; } return tail; } /** * method to get the length of linked list * * @return length i.e. number of nodes in linked list */ public int length() { int length = 0; Node current = head; while (current != null) { length++; current = current.next; } return length; } /** * to get the nth node from end * * @param n * @return nth node from last */ public String getLastNode(int n) { Node fast = head; Node slow = head; int start = 1; while (fast.next != null) { fast = fast.next; start++; if (start > n) { slow = slow.next; } } return slow.data; } @Override public String toString() { StringBuilder sb = new StringBuilder(); Node current = head; while (current != null) { sb.append(current).append("-->"); current = current.next; } if (sb.length() >= 3) { sb.delete(sb.length() - 3, sb.length()); } return sb.toString(); } } Output linked list : 1-->2-->3-->4 the first node from last: 4 the second node from the end: 3 the third node from the tail: 2

That's all about how to find the 3rd element from last in a linked list in Java. We have solved the program in one pass by using two pointer approach, also known as tortoise and hare algorithm because one pointer is slower than others. It is one of the useful technique to know because you can use the same algorithm to detect a cycle in the linked list, as shown here. You can also use this algorithm creatively in newer problems where you need to traverse the linked list and manipulating multiple nodes at the same time

Btw, this is one of many data structure and algorithm based problems you will see in a typical programming job interview(seeCracking the Coding Interviews). Since the linked list is a popular data structure, questions like cycle detection and finding length of linked lists are quite popular along with this one and here are some more useful online courses to prepare for your Programming Job interviews and improve your understanding of key data structure and Algorithms of Computer Science.

Further Learning

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java: An Interview Refresher

Related Data Structure and Algorithm Interview Questions from Javarevisited Blog

• How to reverse a singly linked list without recursion in Java (solution)
• How to find if a singly linked list contains a loop? (solution)
• Top 30 linked list coding interview questions (see here)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• Top 20 String coding interview questions (see here)
• When to use ArrayList vs LinkedList in Java? (answer)
• How to find the first and last element of a linked list in Java? (solution)
• How to convert a linked list to an array in Java? (example)
• How to search element inside a linked list in Java? (solution)
• Top 15 Data Structure and Algorithm Interview Questions (see here)
• What is the difference between LinkedList and ArrayList in Java? (answer)
• Top 30 Array Coding Interview Questions with Answers (see here)
• Top 50 Java Programs from Coding Interviews (see here)
• 5 Free Data Structure and Algorithms Courses for Programmers (courses)
• 10 Algorithms Books Every Programmer Should read (books)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this article then please share with your friends and colleagues. If you have any question or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Easy to Advanced Data Structures course on Udemy.