Finding the 3rd item from the end of a linked list in Java

From the translator:

This article is a translation of an article published on the javarevisited blog. It can be interesting both for beginners and experienced programmers when preparing for interviews. In the future, it is planned to translate a cycle of articles on algorithms and recipes for solving problems of both typical and academic nature. We are pleased to accept constructive suggestions and comments both on the quality of translation and on the choice of new articles.

Finding the 3rd element from the end in a single-linked list or the n-th node from the tail is one of the tricky and frequently asked questions on the problems of single-linked lists at interviews. The task, in this case, is to solve the problem in just one run of the cycle, i.e., you cannot walk through the linked list again and you cannot go backwards, because the list is simply connected. If you have ever solved the problems of linked lists, for example, finding the length , inserting or deleting elements, you should already be familiar with the question of traversing lists. In this article, we use the same algorithm that we used to find the middle element of a linked list in one loop pass . This algorithm is also known as the “tortoise and hare algorithm” due to the speed of two pointers used by the algorithm to bypass a simply linked list.

If you remember, the algorithm uses two pointers - fast and slow. A slow pointer starts a detour when the fast one reaches the Nth element, for example, to find the 3rd item from the end, the second pointer starts the detour when the first pointer reaches the 3rd item.
')
After that, both pointers move one step per iteration until the first pointer points to null , indicating that the end of the linked list has been reached. At this point, the second pointer points to the 3rd or Nth node from the end. The problem is solved, you can either output the node value, or return the link to the caller according to your requirements.

This is one of the many problems of data structures and algorithmic problems that you will encounter in a typical interview (see Cracking the Coding Interviews ). Since a linked list is a popular data structure, questions on finding in a loop and determining the length of linked lists, as well as the ones covered in this article, are quite popular.

Java program for finding the Nth node from the tail of a linked list

The following is a complete listing of the Java program for finding the Nth item from the end of a single-linked list. This program solves the problem in a single pass, i.e., bypassing the linked list is performed only once. As you can see, we used just one while loop in the getLastNode method (int n). This method takes an integer parameter and can be used to find the nth item from the end of a linked list, for example, for the 2nd item from the tail, 2 steps are needed, and to get the 3rd item in the list - 3.

The SinglyLinkedList class is a single-valued list in Java. This is the same class that we used earlier in articles about single-linked lists, for example, about the implementation of a linked list in Java. This is a collection of the Node class, which is a linked list node. It contains a piece of data and a link to the next node. The SinglyLinkedList class also contains a link to the head, i.e. the first node of the linked list.

The following is a visual explanation of finding the 2nd item from the tail of a simply linked list. You can see how the fast and slow pointers pass through the list, and when the fast pointer points to the tail, the slow one points to the nth node from the end.


As a programmer, you should know the basic data structures and algorithms, for example, what a coherent list is, its advantages and disadvantages and when to use it, for example, it is good for frequently adding and deleting elements, but not so good for searching, because . searching for an item in a linked list takes O (n) time. You can read more about linked lists in good books about data structures and algorithms, such as Introduction to the algorithms of Thomas H. Kormen - one of the best books to study this topic.

At first, you may not like this book, as it is a bit difficult to understand because of the topic and style of presentation, but you must follow it and refer to it from time to time to understand key data structures, such as arrays, linked lists, trees etc.

Nth node from the end in a single-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("  : " + list); System.out.println("   : " + list.getLastNode(1)); System.out.println("   : " + list.getLastNode(2)); System.out.println("   : " + list.getLastNode(3)); } } /** *         Java * * @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; //  -      /** * ,    * * @ true    , ..,   */ public boolean isEmpty() { return length() == 0; } /** *       * * @param data */ public void append(String data) { if (head == null) { head = new Node(data); return; } tail().next = new Node(data); } /** *         * * @return   */ private Node tail() { Node tail = head; //     ,    while (tail.next != null) { tail = tail.next; } return tail; } /** *      * * @return , .,      */ public int length() { int length = 0; Node current = head; while (current != null) { length++; current = current.next; } return length; } /** *  n-    * * @param n * @return n-    */ 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(); } } 

Conclusion
linked list: 1 -> 2 -> 3 -> 4
first node from end: 4
second node from end: 3
the third node from the tail:

That's all about finding the 3rd item from the end of a linked list in Java . We wrote a program that solves the problem in a single pass using the two-pointer approach, also known as the hare and turtle algorithm, since one pointer is slower than the second. This is one of the useful tricks, because You can use the same algorithm to define a loop in a linked list, as shown here . You can also creatively use this algorithm to solve other problems when you need to go around the linked list and manipulate nodes at the same time.