Nth node from the end of the Linked list in Java

In talks with leading IT organizations like Google, Amazon, TCS, Accenture, etc., this extremely intriguing subject is constantly brought up. The goal of the problem-solving exercise is to evaluate the interviewee's logical reasoning, critical thinking, and problem-solving abilities. The n-th node first from the end of a LinkedList will therefore be obtained in this section using various methods and logic. Additionally, we'll write Java programs for the same.

Problem  Statement

There is a value N and a singly linked list provided. The number of the Nth node out from the end must be calculated as our task. The end indicates that the reference point is taken as from the rightmost node, which complicates the issue. It's because there is only one way to explore a singly linked list. Keep in mind that N will always be less than as well as equal to the length of a linked list. Take note of the examples below.

Example 1:

Input: 18 -> 57 -> 47 -> 33 -> 11 -> 75 -> 65 -> 98 -> NULL, N = 2

Output: 65

Explanation: Node 65 is the second node as from the end of the provided linked list.

Example 2:

Input: 19 -> 56 -> 154 -> 12 -> 10 -> 70 -> 66 -> 30 -> NULL, N = 5

Output: 12

Explanation: Node 12 is the fifth node as from the end of the provided linked list.

Solution to the Problem Using Stack as an approach

The Last in First Out (LIFO) principle governs how stacks operate. So, whenever it's necessary to calculate the nth node as from the end of such a linked list, a stack comes in handy. All we need to do is place every node in the stack, then take out n nodes at a time. We provide the value of an nth deleted node.

NthEndNode.java

import java.util.Stack;  
class LLNode    
{    
int v;    
LLNode next;    
// Taking n as its argument 
// in the class node function Object() { [native code] }  
LLNode(int n)    
{    
this.v = n;    
this.next = null;    
}    
}   
public class NthEndNode   
{  
public int findNthFromEnd(LLNode h1, int n1)  
{  
Stack<Integer> st = new Stack<Integer>();  
LLNode ptr = h1;  
while(ptr != null)  
{  
    st.push(ptr.v);  
    ptr = ptr.next;  
}  
int v = 0;  
while(n1 != 0)  
{  
v = st.peek();  
st.pop();  
n1 = n1 - 1;  
}  
return v;  
}  
// Driver code  
public static void main(String[] args)  
{  
// creating an instance for the class NthEndNode  
NthEndNode o = new NthEndNode();  
// Giving the first input  
int n1 = 2;  
// the topmost node in the linked list, or its first node.   
LLNode h1 = new LLNode(19);  
// remainder of the linked list's nodes   
h1.next = new LLNode(57);    
h1.next.next = new LLNode(44);    
h1.next.next.next = new LLNode(34);    
h1.next.next.next.next = new LLNode(11);    
h1.next.next.next.next.next = new LLNode(77);
// h1.next.next.next.next.next.next.next = new LLNode(30);      
int a = o.findNthFromEnd(h1, n1);  
System.out.println(" Regarding the subsequent linked list ");  
while(h1 != null)  
{  
    System.out.print(h1.v + " ");  
    h1 = h1.next;  
}  
System.out.println();  
System.out.println(" The " + n1 + "nd node from the end of the LinkedList is: " + a);  
h1 = null;  
System.out.println( "\n");  
// input 2  
n1 = 5;  
// the topmost node in the linked list, or its first node.   
h1 = new LLNode(19);  
// remainder of the linked list's nodes    
h1.next = new LLNode(11);    
h1.next.next = new LLNode(56);    
h1.next.next.next = new LLNode(51);    
h1.next.next.next.next = new LLNode(32);    
h1.next.next.next.next.next = new LLNode(10);  
h1.next.next.next.next.next.next = new LLNode(70);   
// h1.next.next.next.next.next.next.next = new LLNode(30);  
a = o.findNthFromEnd(h1, n1);  
System.out.println(" Regarding the subsequent linked list  ");  
while(h1 != null)  
{  
    System.out.print(h1.v + " ");  
    h1 = h1.next;  
}  
System.out.println();  
System.out.println(" The " + n1 + "th node from the end of the LinkedList is: " + a);  
}  
}  

Output:

Analysis of Complexity: The aforementioned program's time complexity is O (s). The program's space complexity is O(s), where s is indeed the total number of nodes in the specified linked list, and because the program uses a stack to store the nodes.

In terms of spatial complexity, we can still make some improvements. Keep in mind the following strategy.

Utilizing the Size of a Linked List as a Method

We are aware that moving from left to right via a singly linked list is simple. In the above method, we used the stack to traverse the linked list in the reverse direction. If we closely examine the linked list, we can see that the second node from the final is the fifth node from the start, and the fifth node as from the end is the second node from the start (see example 1). (see example 2). We may determine a formula for calculating the nth node from the finish by considering these two examples. The equation is:

The node that is (s - n + 1)th from the beginning, which is the number of nodes in the linked list, is the node that is (nth) from the end. As a result, the 6 - 2 + 1 = 5th node from the beginning is the 2nd node from the finish (6 is the size of the linked list mentioned in example 1). The strategy is therefore straightforward. The linked list's total size needs to be calculated, and that's all. Watch the program that follows.

// NthEndNode1.java

import java.util.Stack;  
class LLNode    
{    
int val;    
LLNode next;    
// Taking n as its argument 
// in the class node function Object() 
// { [native code] } 
LLNode(int n)    
{    
this.val = n;    
this.next = null;    
}    
}   
public class NthEndNode1   
{  
public int findNthFromEnd(LLNode h1, int n1)  
{  
LLNode p = h1;  
int s = 0;  
// calculating the size of the linked list  
while(p != null)  
{  
    s = s + 1;  
    p = p.next;  
}  
// According to the strategy, we must begin at the beginning.
int v = s - n1 + 1;  
// Because h1 has already been pointing to the root node, 
// v!= 1.  
while(v != 1)  
{  
    v = v - 1;  
    h1 = h1.next;  
}  
return h1.val;  
}  
// Driver code  
public static void main(String[] args)  
{  
// creating an instance for the class NthEndNode1  
NthEndNode1 o = new NthEndNode1();  
// Giving the first input  
int n1 = 2;  
// the topmost node in the linked list, or its first node.   
LLNode h1 = new LLNode(19);  
// remainder of the linked list's nodes   
h1.next = new LLNode(57);    
h1.next.next = new LLNode(44);    
h1.next.next.next = new LLNode(34);    
h1.next.next.next.next = new LLNode(11);    
h1.next.next.next.next.next = new LLNode(77);
// h1.next.next.next.next.next.next.next = new LLNode(30);      
int a = o.findNthFromEnd(h1, n1);  
System.out.println(" Regarding the subsequent linked list ");  
while(h1 != null)  
{  
    System.out.print(h1.val + " ");  
    h1 = h1.next;  
}  
System.out.println();  
System.out.println(" The " + n1 + "nd node from the end of the LinkedList is: " + a);  
h1 = null;  
System.out.println( "\n");  
// input 2  
n1 = 5;  
// the topmost node in the linked list, or its first node.   
h1 = new LLNode(19);  
// remainder of the linked list's nodes    
h1.next = new LLNode(11);    
h1.next.next = new LLNode(56);    
h1.next.next.next = new LLNode(51);    
h1.next.next.next.next = new LLNode(32);    
h1.next.next.next.next.next = new LLNode(10);  
h1.next.next.next.next.next.next = new LLNode(70);   
// h1.next.next.next.next.next.next.next = new LLNode(30);  
a = o.findNthFromEnd(h1, n1);  
System.out.println(" Regarding the subsequent linked list  ");  
while(h1 != null)  
{  
    System.out.print(h1.val + " ");  
    h1 = h1.next;  
}  
System.out.println();  
System.out.println(" The " + n1 + "th node from the end of the LinkedList is: " + a);  
}  
}  

Output:

Analysis of Complexity: The program mentioned above has the same level of temporal complexity as the one before it. The program's space complexity is O because it doesn't use any data structures (1).