Home » Nth Node from The End of a Linked List in Java

Nth Node from The End of a Linked List in Java

by Online Tutorials Library

Nth Node from The End of a Linked List in Java

It is very interesting problem frequently asked in interviews of top IT companies like Google, Amazon, TCS, Accenture, etc. By solving the problem, one wants to check the logical ability, critical thinking, and problem-solving skill of the interviewee. So, in this section, we are going to get the n-th node from the end of a LinkedList in Java with different approaches and logic. Also, we will create Java programs for the same.

Problem Statement

A singly linked list and a value N are given. Our task is to compute the value of the Nth node from the end. The end means the reference point is taken from the rightmost node, and it makes the problem tricky. It is because, in a singly linked list, one can only traverse in one direction. Note the value of N is always going to be less than or equal to the size of the linked list. Observe the following examples.

Example 1:

Input: 19 -> 56 -> 45 -> 32 -> 10 -> 70 -> NULL, N = 2

Output: 10

Explanation: The second node from the end of the given linked list is node 10.

Example 2:

Input: 119 -> 156 -> 15 -> 312 -> 101 -> 710 -> NULL, N = 5

Output: 156

Explanation: The fifth node from the end of the given linked list is node 156.

Solution to the Problem

Approach: Using Stack

We know that a stack work in a Last In First Out (LIFO) manner. Therefore, a stack works well whenever one has to compute the nth node from the end of a linked list. All we have to do is to store all the nodes in the stack and then remove the n nodes from the stack. The value of the nth removed node is our answer.

FileName: NthNodeEnd.java

Output:

For the following linked list  19 56 45 32 10 70   The 2nd node from the end is: 10    For the following linked list  19 119 156 15 312 101 710   The 5th node from the end is: 156  

Complexity Analysis: The time complexity of the above program is O(s). Since the program is using a stack for storing the nodes, the space complexity of the program is also O(s), where s is the total number of nodes present in the given linked list.

We can still do some optimization in terms of space complexity. Observe the following approach.

Approach: Using the Size of The Linked List

We know that it is easy to traverse a singly linked list from left to write. In order to traverse the linked list in the opposite direction, we used the stack in the above approach. If we observe the linked list carefully, we find that the 2nd node from the last is the 5th node from the beginning (see example 1), and the 5th node from the end is the 2nd node from the beginning (see example 2). By looking at these two examples, we can deduce a formula for computing the nth node from the end. The formula is:

Nth node from the end is the (s – n + 1)th node from the beginning, where is the total number of nodes present in the linked list. Thus, the 2nd node from the end is the (6 – 2 + 1) = 5th node from the beginning (6 is the size of the linked list mentioned in example 1). Thus, the approach is simple. All we have to do is to compute the total size of the linked list. Observe the following program.

FileName: NthNodeEnd.java

Output:

For the following linked list  19 56 45 32 10 70   The 2nd node from the end is: 10    For the following linked list  19 119 156 15 312 101 710   The 5th node from the end is: 156  

Complexity Analysis: The time complexity of the above program is the same as the previous one. Since the program is not using any data structure, the space complexity of the program is O(1).


You may also like