In this tutorial, we have a linked list and we have to find Nth element from the end linked list .
Example:
in above example , if we have to find 2nd element from end linked list then output is 4
Program to find the Nth element from the end linked list
In this approach, we will use two variables to represent slow and fast pointers. The fast variable moves first, while the slow one begins when fast reached Kth node. This means that when the fast variable comes to the end, the slow will come to the step (end-K) and will point to the Kth node from the end.
public class KthNodeFromEndLinkedList {
public static void main(String a[]) {
Node firstNode = new Node(10);
Node secondNode = new Node(20);
Node thirdNode = new Node(30);
Node fourthNode = new Node(40);
Node fifthNode = new Node(50);
Node sixthNode = new Node(60);
Node head = firstNode;
head.setNext(secondNode);
secondNode.setNext(thirdNode);
thirdNode.setNext(fourthNode);
fourthNode.setNext(fifthNode);
fifthNode.setNext(sixthNode);
System.out.println("3rd element from tail in linked list : " + getNthNodeFromEnd(head, 3));
System.out.println("4th element from end in linked list : " + getNthNodeFromEnd(head, 4));
System.out.println("5th element from end in linked list : " + getNthNodeFromEnd(head, 5));
}
public static Node getNthNodeFromEnd(Node head, int n) {
Node fast = head;
Node slow = head;
for (int i = 1; i <= n; i++) {
fast = fast.getNextNode();
}
while (fast != null) {
fast = fast.getNextNode();
slow = slow.getNextNode();
}
return slow;
}
}
class Node {
private Node next;
private int data;
public Node(int data) {
this.data = data;
}
public int getData() {
return data;
}
public Node getNextNode() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return String.format("%d", data);
}
}
Output
3rd element from tail in linked list : 40 4th element from end in linked list : 30 5th element from end in linked list : 20
