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 :