Linked List

Find last Nth node from singly linked list using single iteration

Pinterest LinkedIn Tumblr

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

  1. 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?

  2. How come you do not have your website viewable in mobile format? cant see anything in my Droid. Angie Fremont Glory

  3. Hi there colleagues, pleasant piece of writing and good arguments commented at this place, I am really enjoying by these. Chiquita Lucias Merrili

  4. 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

  5. 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

  6. I am sure this paragraph has touched all the internet people, its really really fastidious paragraph on building up new website. Marcela Ban Boothman

Write A Comment