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.

3rd node from the end in linked list Java algorithm


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.

How to find Nth node from end in linked list Java

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[]) {
    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 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

Other linked list based questions from Java Interviews
  • How to reverse a singly linked list in Java? (solution)
  • What is difference between ArrayList and LinkedList in Java? (answer)
  • How to find the first and last element of linked list in Java? (solution)
  • Difference between array and linked list data structure? (answer)
  • How to implement linked list in Java using Generics? (solution)
  • When to use ArrayList over LinkedList in Java? (answer)

1 comment :

Anonymous said...

I was asked how to find the 2nd element from the last in a singly linked list in recent interview. Follow-up question was how do you detect the cycle on linked list i.e. where one of the node points to previous node in singly linked list. I was manage to answer both of them but stuck when they asked, how do you find the start of the cycle? Do you know how to solve this problem? Can the two pointer approach also give you starting node of cycle?

Post a Comment