Program for find n’th node from the end of a Linked List

Question: Given a Linked List and a number n, write a program that finds the value at the nth node from the end of the Linked List.

Method 1 – Use length of linked list

1.   Calculate the length of Linked List. Follow this tutorial Find Length of a Linked List data

2.   Print the (len – n + 1)th node from the beginning of the Linked List.

for (int i = 1; i < length - nthNode + 1; i++)

Code in Java

package in.eyehunt.data.struc;
public class LinkedList {

    Node head; // head of list
    // Linked list Node.
    class Node {
        int data;
        Node next;
        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }
    void push(int n) {
        //create new node
        Node newNode = new Node(n);
        // next node is head
        newNode.next = head;
        // move had point to new node
        head = newNode;
    }
    void findNthNode(int nthNode) {
        Node findNode = head;
        int length = count();
        if (head == null) {
            System.out.println("LinkedList is null");
        } else if (nthNode > length) {
            System.out.println("\nFinding nth node not existing in List");
        } else {
            for (int i = 1; i < length - nthNode + 1; i++)
                findNode = findNode.next;
            System.out.println("\nnth node in list from end is " + findNode.data);
        }
    }
    //Returns count of nodes in linked list (iteration)
    public int count() {
        int a = 0;
        Node n = head;
        while (n != null) {
            n = n.next;
            a++;
        }
        return a;
    }
    void printAllNodes() {
        Node node = head;
        System.out.print("Given Linked list : ");
        while (node != null) {
            System.out.print("-> " + node.data);
            node = node.next;
        }
    }
    public static void main(String a[]) {
        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.push(1);
        linkedList.push(9);
        linkedList.push(7);
        linkedList.push(2);
        linkedList.push(4);
        linkedList.printAllNodes();
        linkedList.findNthNode(9);
    }
}

Output :

Given Linked list : -> 4-> 2-> 7-> 9-> 1
nth node in list from end is 9

Time Complexity: O(n) where n is the length of linked list.

Here is more LinkedList interview questions :

1. Reverse a Linked list data structure in java
2. Find the middle of a given linked list data structure
3. Inserting a new node in a linked list data structure
4. Find Length of a Linked List data structure (Iterative and Recursive)