How to find the nth Last node of a Singly LinkedList ?

Generally, LinkedList means a Singly LinkedList. This list consists of a number of nodes where each node has a next pointer to the following node. The link of the last node in the list is NULL, which indicates the end of the list. Following figure describes such a singly LinkedList.

Following is the type declaration we are going to use for our example.

We have a Node.java class, which represent a single node in the LinkedList.

package com.algo.linkedlist;

public class Node {

 int data;
 Node next;

 public Node(int data) {
  this.data = data;
  this.next = null;
 }

 public void print() {
  System.out.print(this.data);
 }
}

Following is the LinkedList ADT created using the nodes. Where we will pass the number of nodes in the list and in turn it will create a LinkedList with specified size.

package com.algo.linkedlist;

public class LinkedList {

 Node head;

 public LinkedList(int size) {
  head = new Node(1);
  Node tempNode = null;
  for (int i = 2; i <= size; i++) {
   Node node = new Node(i);
   if (i == 2) {
    head.next = node;
    tempNode = head.next;
   } else {
    tempNode.next = node;
    tempNode = node;
   }
  }
 }
}

Now we are going to find the nth  last node of the LinkedList. If we are interested to find the 2nd last node of the above list in figure, then that will be the node with value 36.

Using a Map:

The problem can be solved using a HashMap. In this approach we are going to create a HashMap whose keys are the position of the node and values are the node itself. Such an entry of the HashMap will look like <position_of_the_node, Node>. Following figure is representing such a HashMap created from the LinkedList given in the above figure.

Index of the Node  Node
1  Node with value 10
2 Node with value 15
3 Node with value 36
4 Node with value 7

When we have completed the traversal of the LinkedList to create the HashMap, we have the list’s length. The LinkedList’s length can be defined as map.size(). Let us consider the LinkedList length is M. To find the nth element from end we can convert this to (M-n+1) from the beginning. Since we already know the length of the LinkedList, then we can return the (M-n+1)th  key’s value from the HashMap to get the result. Following is the code to get the nth last node in this approach.

public Node getNthLastNodeUsingMap(Node head, int n) {
  Map<Integer, Node> nodeByIndex = new HashMap<>();
  int index = 1;
  while (head != null) {
	nodeByIndex.put(index, head);
	head = head.next;
	index++;
  }
  int nthLastElementIndex = (nodeByIndex.size() - n + 1);
  return nodeByIndex.get(nthLastElementIndex);
}

Time Complexity: Time for creating the HashMap is T(m) = O(m). Space complexity: O(m). Since, we need to create a HashMap of size m.

By Two scans of the LinkedList:

Can we solve the problem more efficiently ? Yes, if we observe the earlier solution, we can see that actually we are finding the length of the LinkedList by creating the HashMap. We can find the length of the LinkedList by just starting at the head node and traversing the list once. So, we can find the length of the LinkedList without creating the HashMap. Following piece of code is actually used to find the length of the list in such a way:

public int length(Node head) {
  int length = 0;
  while (head != null) {
    length++;
    head = head.next;
  }
  return length;
}

After finding the length of the LinkedList compute (M-n+1) and with one more scan from the beginning of the list we can find the (M-n+1)th  node from the LinkedList, which is our desired node. This solution needs two scans of the LinkedList. One for finding the length of the list and another for finding the (M-n+1)th node from the LinkedList. Following piece of code is the implementation of this approach:

public Node getNthLastNodeByTwoScan(Node head, int n) {
  int length = length(head);
  int index = (length - n + 1);
  for (int i = 1; i < index; i++) {
    head = head.next;
  }
  return head;
}

Time Complexity: Time for finding the length of the LinkedList is O(n) and finding the (M-n+1)th  node is O(n). So the total time complexity is O(n)+ O(n) = O(n). And Space Complexity is O(1) as we don’t need to use any extra space.

Solve the problem with a Single Scan:

Can we do better to get the solution. Can we solve the problem with a single scan? The answer is Yes; we need to use 2 pointers for the solution. Initially both the pointers will point to the head of the LinkedList. First pointer will make n number of moves while the second still pointing to the head. Now both the pointers will move one step forward in each move. As a result, the second pointer will point to the nth last node when the first reaches the end of the list. The following code is the implementation of this approach.

public Node getNthLastNodeByOneScan(Node head, int n) {
 Node ptr1 = head, ptr2 = null;
 // First pointer is making n number of moves
 for (int i = 1; i < n; i++) {
  if (ptr1 != null) {
   ptr1 = ptr1.next;
  }
 }
 // Now both pointer will make a move until
 // ptr1 reaches the end of the list
 while (ptr1 != null) {
  if (ptr2 == null) {
   ptr2 = head;
  } else {
   ptr2 = ptr2.next;
  }
  ptr1 = ptr1.next;
 }
 if (ptr2 != null) {
  return ptr2;
 }
 return null;
}

Time Complexity: The time complexity of this approach is O(n) and the space complexity is O(1).

Now let us give the whole code to run this example:

1. Node.java is a single node of the LinkedList. This class is already given at the beginning of this tutorial.  

2. LinkedList.java ADT created using the nodes. Where we will pass the number of nodes in the list and in turn it will create a LinkedList with specified size. This class is also given at the beginning of this tutorial. 

3. LinkedListUtility.java, which contains all the utility methods used in this tutorial.

package com.algo.linkedlist;

import java.util.HashMap;
import java.util.Map;

public class LinkedListUtility {

 public void print(Node head) {
  while (head != null) {
   head.print();
   head = head.next;
   if (head != null) {
    System.out.print(" --> ");
   }
  }
 }

 public int length(Node head) {
  int length = 0;
  while (head != null) {
   length++;
   head = head.next;
  }
  return length;
 }

 public Node getNthLastNodeUsingMap(Node head, int n) {
  Map < Integer, Node > nodeByIndex = new HashMap < > ();
  int index = 1;
  while (head != null) {
   nodeByIndex.put(index, head);
   head = head.next;
   index++;
  }
  int nthLastElementIndex = (nodeByIndex.size() - n + 1);
  return nodeByIndex.get(nthLastElementIndex);
 }

 public Node getNthLastNodeByTwoScan(Node head, int n) {
  int length = length(head);
  int index = (length - n + 1);
  for (int i = 1; i < index; i++) {
   head = head.next;
  }
  return head;
 }

 public Node getNthLastNodeByOneScan(Node head, int n) {
  Node ptr1 = head, ptr2 = null;
  // First pointer is making n number of moves
  for (int i = 1; i < n; i++) {
   if (ptr1 != null) {
    ptr1 = ptr1.next;
   }
  }
  // Now both pointer will make a move until
  // ptr1 reaches the end of the list
  while (ptr1 != null) {
   if (ptr2 == null) {
    ptr2 = head;
   } else {
    ptr2 = ptr2.next;
   }
   ptr1 = ptr1.next;
  }
  if (ptr2 != null) {
   return ptr2;
  }
  return null;
 }
}

4. TestLinkedList.java, for testing all the utility methods in this tutorial.

package com.algo.linkedlist;

public class TestLinkedList {

  public static void main(String[] args) {
	LinkedList linkedList = new LinkedList(10);
	LinkedListUtility linkedListUtility = new LinkedListUtility();
	linkedListUtility.print(linkedList.head);
	lineBreak();
	System.out.println("Length of the LinkedList is >>" +
		linkedListUtility.length(linkedList.head));
	Node nthLastNode = linkedListUtility.getNthLastNodeUsingMap(linkedList.head, 3);
	System.out.print("3rd last node of the LinkedList using HashTable is : ");
	nthLastNode.print();
	lineBreak();
	nthLastNode = linkedListUtility.getNthLastNodeByTwoScan(linkedList.head, 3);
	System.out.print("3rd last node of the LinkedList using Two scans is : ");
	nthLastNode.print();
	lineBreak();
	nthLastNode = linkedListUtility.getNthLastNodeByOneScan(linkedList.head, 3);
	System.out.print("3rd last node of the LinkedList using One scans is : ");
	nthLastNode.print();
  }

  public static void lineBreak() {
	System.out.println();
  }
}

Output of the program is:

1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 10
Length of the LinkedList is >>10
3rd last node of the LinkedList using HashTable is : 8
3rd last node of the LinkedList using Two scans is : 8
3rd last node of the LinkedList using One scans is : 8

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself