How to find the 3rd (Kth) Node from end of linked list in Java? Fast and Slow Pointer Example [Solved]

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 like finding the length, inserting elements, or deleting elements then you should be familiar with how to traverse through a linked list. Here, we'll use the tortoise and hare algorithm to solve this problem. This is the same algorithm that we have used to find the middle element of the 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 wins 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 the Nth or Kth node. For example, in order to find the 3rd element from the last, the second or slow pointer should start when the first pointer has reached 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.

How to find the Kth Node from the tail of a linked list using fast and slow pointers Pattern in Java

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 that we have used earlier linked list articles like writing your own linked list in Java. 

It is a collection of Node class which represents a node in the linked list. It contains a data part and a reference to the next node. The SinglyLinkedList class also contains a reference to the 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 a 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 the 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 courses 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 to. 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.

How to Find kth Node from the End in a Singly linked list in Java - Example

Here is the complete Java program to solve the problem of finding the kth node from the last in a given single 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 the tortoise and hare algorithm because one pointer is slower than others.

It is one of the useful techniques 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  

It's one of the essential coding patterns and if want to learn more of such patterns, I highly recommend Grokking the Coding Interview: Patterns for Coding Questions course on Educative. which will teach you 15 such coding patterns to crack interviews like the Sliding window, Merge Interval and many other patterns. 

Btw, this is one of many data structure and algorithm based problems you will see in a typical programming job interview(see Cracking the Coding Interviews). 

Since the linked list is a popular data structure, questions like cycle detection and finding the 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.


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)
• 20+ Binary Tree Coding Problems from interviews (Questions)
• How to find the first and last element of a linked list in Java? (solution)
• 7 Best Data Structure and Algorithms Courses (best courses)
• How to convert a linked list to an array in Java? (example)
• How to search elements 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 linked list article then please share it with your friends and colleagues. If you have any questions 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 Algorithm courses to improve your understanding of Data Structure and Algorithms, then you should also check the Data Structures in Java for Beginners a free course on Udemy.

And lastly one question for you, what was the last linked list based question  asked to you on coding interview? was it reverse a singly linked list, find if linked list has cycle or this one or something else? Do let me know in comments.