# 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.

If you remember the algorithm uses two pointers, fast and slow. The slow pointer starts when fast pointer is reached to Nth element e.g. In order to find the 3rd element from last, the second pointer will start when the first pointer will reach the 3rd 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. You have solved the problem, you can either print value of node or return reference to the caller based upon your requirement.

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 linked list is a popular data structure, questions like cycle detection and finding length of linked lists are quite popular along with this one.

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

Here is our complete Java program to find the Nth element from last in a singly linked list in Java. This program solves this program in one pass i.e. 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 linked list e.g. to get the 2nd element from tail, pass 2 and to get the 3rd element from the list, pass 3.

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

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

As a programmer, you should know  key data structures and algorithms e.g. what is a linked list data structure, it's pros and cons and when to use linked list e.g. it is good for frequently adding and removing element but not so good for search as it take O(n) time to find an element inside linked list. You can read more about linked list in a good data structure and algorithm books like Introduction to Algorithms by Thomas H. Cormen, one of the best book to learn data structures and algorithms.

Initially, you may not like this book as it is 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 e.g. array, linked list, trees etc.

Nth node from then end in Singly linked list

```public class Practice {

public static void main(String args[]) {
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
*
*/
static class Node {
private Node next;
private String data;

public Node(String data) {
this.data = data;
}

@Override
public String toString() {
return data.toString();
}
}

/**
* 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) {
return;
}
tail().next = new Node(data);
}

/**
* returns the last node or tail of this linked list
*
* @return last node
*/
private Node tail() {
// 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;

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) {
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();

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
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 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 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 same time

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz

Other linked list based questions from Java Interviews
• How to reverse a singly linked list in Java? (solution)