Write a program to find last Nth node from singly linked list using single iteration. Linked list do not use index and uses only reference to next item.
Algorithm Explanation
 | Take two pointers for finding the last Nth node. Slow pointer and fast pointer initialize with head pointer. |
| Move fast pointer to Nth node. |
| Iterate both slow pointer and fast pointer till end of the linked list. When the fast pointer move to end of linked list, the slow pointer point to last Nth node |
| Return the element to display the data |
Source Code
package com.dsacode.DataStructre.linkedlist;
class Node{
public int val;
public Node nextNode;
public Node(int x) {
val = x;
nextNode = null;
}
}
public class FindLastNth {
static Node FindnthToLast(Node head, int n) {
if (n < 1 || head == null)
return null;
Node pntr1 = head, pntr2 = head;
for (int i = 0; i < n - 1; ++i) {
if (pntr2 == null)
return null;
else
pntr2 = pntr2.nextNode;
}
while(pntr2.nextNode != null ){
pntr1 = pntr1.nextNode;
pntr2 = pntr2.nextNode;
}
return pntr1;
}
public static void main(String[] args) {
System.out.println("Insert itmes in LinkedList:9, 43, 34, 11, 78, 55");
Node n1 = new Node(9);
Node n2 = new Node(43);
Node n3 = new Node(34);
Node n4 = new Node(11);
Node n5 = new Node(78);
Node n6 = new Node(55);
Node n7=null;
n1.nextNode = n2;
n2.nextNode = n3;
n3.nextNode = n4;
n4.nextNode = n5;
n5.nextNode = n6;
n6.nextNode=n7;
printList(n1);
System.out.println("Last 3 rd Item from linked list using single iteration:"+ FindnthToLast(n1,3).val);
}
public static void printList(Node x) {
if(x != null){
System.out.print(x.val + "->");
while (x.nextNode != null) {
System.out.print(x.nextNode.val + "->");
x = x.nextNode;
}
System.out.println("NULL");
}
}
}
Output
Insert items in LinkedList:9, 43, 34, 11, 78, 55 9->43->34->11->78->55->NULL Last 3 rd Item from linked list using single iteration:11
15 Comments
Thank you for the auspicious writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you! By the way, how can we communicate?
Article writing is also a excitement, if you know then you can write
if not it is complicated to write.
How come you do not have your website viewable in mobile format? cant see anything in my Droid. Angie Fremont Glory
I was able to find good information from your content. Candie Guss Houser
Some genuinely superb articles on this web site , appreciate it for contribution. Enid Eamon Serg
Would love to constantly get updated great web blog ! . Kacie Josh Barmen
You have brought up a very wonderful details , thankyou for the post. Frances Fidole Cerell
Hi there colleagues, pleasant piece of writing and good arguments commented at this place, I am really enjoying by these. Chiquita Lucias Merrili
Good post. I am facing a few of these issues as well.. Malissia Kile Sikorski
These are all beautiful. We may head up that way this summer to take it all in. I am trying to come up with some fun things to do over the weekends. Vikky Dmitri Tenenbaum
Great delivery. Solid arguments. Keep up the great effort. Verna Chane Blondelle
I really liked your blog article. Much thanks again. Fantastic. Shana Ferris Gordan
Purring is a way for a cat to assuage itself, just like a human baby will suck their thumb to feel better. Orel Rey Bret
I am sure this paragraph has touched all the internet people, its really really fastidious paragraph on building up new website. Marcela Ban Boothman
Awesome article. Really looking forward to read more. Really Great. Valida Sebastian Elison