Linked List: Program to find the nth node from the end of a linked list


Write a program to find the nth node from the end of the linked list

To find the nth node from the end, first we find the length of linked list.
Then subtract given position from the length to get the result position.
This positon is the required node from the start.
Traverse the linkedlist till that position and get required node

For example,
given linked list is -
10 -> 30 -> 50 -> 60 -> 90 -> 70 -> 40
we want to find the node at 5th position from the end

Length of linked list is 7, subtract 5 from length we get position from start as 2
So the 5th node from the end is the 2nd node from the start
Traverse till 2nd node and get the required output which is node(30)

 
Algorithm
  1. Find the length of the given linked list
  2. If the head is NULL, then return from the function
  3. Create one pointer, say current and point on head
  4. For finding position from start simply subtract given position from length and stored in variable 'mov'
  5. Using for loop traverse till that position and print required node data
 
Complexity

Time Complexity : O(n) , where n is the number of nodes in the linked list
Space Complexity : O(1)

 
Java Code
import java.util.*;

 class FindNodeFromEnd{
         
        class Node {
            // initialising data field and next pointer of node
            int data;
            Node next;
         
            Node(int d) {
                this.data = d;
                this.next = null;
            }
        }
        
        Node head;
     
        // creating a linked list using array
        public void buildLinkedlist(int array[], int noOfNodes) {
            int i;
            Node temp, last;
            temp = new Node(array[0]);
            temp.next = null;
            head = temp;
            last = temp;
            for (i = 1; i < noOfNodes; i++) {
                temp = new Node(array[i]);
                temp.next = null;
                last.next = temp;
                last = temp;
            }
        }
     
        // printing of linkedList
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" -> ", allNodesList));
        }
     
        public int getLength() {
            Node temp = head;
            int count = 1;
            
            while (temp.next != null) {
                temp = temp.next;
                count++;
            }
            
            return count;
        }
     
        public int getNthFromLast(int n) {
            // Your code here
            if (head==null){
                return 0;
            }
            
            Node current = head;
            int mov = getLength() - n;
            
            for (int i = 0; i < mov; i++) {
                current = current.next;
            }
            
            return current.data;
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 10, 30, 50, 60, 90, 70, 40 };
            int numberOfNodes = 7;
            // initialising object of linkedlist class
            FindNodeFromEnd ll = new FindNodeFromEnd();
            ll.buildLinkedlist(linkedlistElements, numberOfNodes);
            System.out.println("Given Linked List ");
            ll.printLinkedlist();
            System.out.println("Element at 2nd position from end is "+ll.getNthFromLast(2));
            System.out.println("Element at 5th position from end is "+ll.getNthFromLast(5));
        }
  }
Output

Given Linked List
10 -> 30 -> 50 -> 60 -> 90 -> 70 -> 40
Element at 2nd position from end is 70
Element at 5th position from end is 50



Thanks for feedback.



Read More....
Clone a Linked List
Find the middle of linked list with odd no of nodes
Check if linked list nodes form a palindrome
Delete a node at specific position from linked list
Delete a node from linked list
Detect if cycle is present in a linked list