How to find 2nd, 3rd or kth element from end in linked list in Java? Example [Solved]

Hello guys, today, I am going to discuss one of the important linked list based coding problems from interviews - how to find the Kth element from the end? This question is also asked as to how do you find the 3rd element from the last of a singly linked list in one pass or write a Java program to find the 5th element from the tail of a given linked list in one iteration. In this article, you will learn the programming technique so that you can solve any variant of this problem, I mean the Kth node from the tail problems and some linked list-based challenges. The difficulty in this question is that you need to solve the problem in one iteration or one pass. This means you cannot traverse the linked list again. I mean you cannot go till the end then traverse back to the Kth element.

Problem: How do you find the 3rd node from the tail in a single list in one pass, which means you cannot traverse the list twice.

Solution: We will use the two pointer approach, one is fast, and the other is slow. The slow pointer starts when fast is pointing to the kth element from the beginning. this way, when the fast pointer reaches or points to the tail of the linked list, the slow pointer would be pointing to the kth element from the tail.

This technique is known as the two-pointer approach, where one pointer is slow and the other is fast. It can be used to solve many linked list-based problems like how to find if the linked list has a cycle and finding the start of the cycle problem. It is also known as the tortoise and hare algorithm, which is self-explanatory if you have heard the tortoise and hare story in childhood.

If you remember, the linked list data structure is nothing but a list of a node, where one node knows where is the next node. Which allows nodes to scatter all over the place in memory. This also means the linked list can grow until there is as little space as a node require is available (theoretically).

This is in stark contrast to the array, where you need contiguous memory, which means you can not create an array of 100 elements if you have two contiguous blocks of memory which can hold 90 and 70 elements, but you can definitely create a linked list of even more than 100 elements with this setup.

Btw, If you are new to the programming world or want to refresh your knowledge about essential data structures like an array, string, linked list, hash table, binary tree, balanced tree, stack, queue, priority queue, etc then I suggest you go through a comprehensive data structure and algorithms course.

If you need a recommendation, I suggest you join Data Structures and Algorithms: Deep Dive Using Java course by Tim Buchalaka on Udemy. It's one of the affordable courses and you can buy it for just $10 on several Udemy sales which happens every now and then. It covers all essential data structures and algorithms like searching, sorting, and graph-based algorithms.

How to find Kth Node From the End in a Linked List?

Without wasting any more of your time, here is our complete Java program to solve this problem in one pass. In this program, I have used two Java variables to represent slow and fast pointers. The fast variable moves first while the slower one starts when the fast reached the Kth element.

This means when fast one will reach the end, slower will reach the end -K step and point to the Kth node from the end. Just like a binary tree, a linked list is a recursive data structure, which means you can also solve most of the linked list-based problems using Recursion. 

If you are preparing for technical interviews then I suggest you should have a good command of Recursion, it's a very useful technique to solve linked lists and binary tree-based coding problems programming. If you need some help, I suggest you go through Recursion for Coding Interviews in Java course on Educative.

Recursion is also used heavily on solving Dynamic Programming based problems, which are often very difficult to solve during coding interviews.

/** 
 * Java Program to find nth node from tail in linked list
 * @author Javin
  */ 
 
 
public class KthNodeFromLastInLinkedList{
 
  
    public static void main(String a[]) {
 
        Node ten = new Node(10); 
        Node twenty = new Node(20); 
        Node thirty = new Node(30); 
        Node fourty = new Node(40); 
        Node fifty = new Node(50); 
        Node sixty = new Node(60);
 
  
        Node head = ten; 
        head.setNext(twenty); 
        twenty.setNext(thirty); 
        thirty.setNext(fourty); 
        fourty.setNext(fifty); 
        fifty.setNext(sixty);
  
 
        // Now our linked list is 
        // 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null
 
 
        System.out.println("2nd element from end in linked list  : " 
                + getNthNodeFromEnd(head, 2));
 
 
        System.out.println("3rd element from tail in linked list  : " 
                + getNthNodeFromEnd(head, 3)); 
 
 
        System.out.println("4th element from end in linked list  : " 
                + getNthNodeFromEnd(head, 4));
 
 
    }
  
    /* 
     * return nth node from tail of linked list 
     */
 
    public static Node getNthNodeFromEnd(Node head, int n){ 
        Node fast = head; 
        Node slow = head; 
        int count = 1; 
 
 
        // let's move fast pointer to n step ahead 
        for(int i = 1; i<=n ; i++){ 
            fast = fast.getNextNode(); 
        }
 
 
        // now let's start moving both fast and slow pointer 
        while(fast != null){ 
            fast = fast.getNextNode(); 
            slow = slow.getNextNode();
         }
 
 
        return slow;
 
    }
 
}
 
 
 
class Node{
 
    private Node next; 
    private int data;
 
  
    public Node(int data){ 
        this.data = data;
 
    }
 
 
    public int getData(){ 
        return data;
 
    }  
 
    public Node getNextNode(){ 
        return next;
     }
 
 
    public void setNext(Node next){ 
        this.next = next;
     }
 
  
    @Override
 
    public String toString() { 
        return String.format("%d", data);
 
    }
 
}
  
 
Output :
 
2nd element from end in linked list  : 50 
3rd element from tail in linked list  : 40 
4th element from end in linked list  : 30

That's all about how to find the kth node from the end in a single list in Java. You can use this trick to solve problems like finding 3rd element from the tail, or 5th element from the tail in coding interviews. This problem also teaches a very important technique to solve linked list-based coding problems, the two-pointer approach. You can use this technique to solve problems like how to find a cycle in a given linked list and others.

Other Data Structure and Coding problems From Interviews which you may like to solve

• How to reverse a String in place in Java? (solution)
• How to find all permutations of a given String in Java? (solution)
• 101 Coding Problems and few tips for Tech interviews (tips)
• When to use ArrayList vs LinkedList in Java? (answer)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• How to remove duplicate characters from String in Java? (solution)
• How to check if a given number is prime or not? (solution)
• 10 Free Courses to learn Data Structure and Algorithms (courses)
• How to find the highest occurring word from a text file in Java? (solution)
• 100+ Data Structure and Algorithms Problems (solved)
• 10 Books to learn Data Structure and Algorithms (books)
• How to check if two given Strings are Anagram in Java? (solution)
• My favorite free courses to learn data Structure in-depth (FreeCodeCamp)
• Top 5 Books to Learn Data Structure and Algorithms (books)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• Top 5 Books for Programming and Coding Interviews (books)
• 10 Data Structure and Algorithms course to crack coding interview (courses)
• How to check if a String contains duplicate characters in Java? (solution)
• How to count vowels and consonants in a given String in Java? (solution)
• 21 String coding Problems from Technical Interviews (questions)
• How to reverse words in a given String in Java? (solution)

Thanks for reading this article so far. If you find this String-based Java coding problem from Google and my explanation useful then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you are preparing for a programming job interview, then you must prepare for an all-important topic like data structure, String, array, etc. One course which can help you with this task is the Grokking the Coding Interview: Patterns for Coding Questions course on Educative.io platform. It contains popular coding interview patterns which will help you to solve most of the problems in your coding interviews.