Java Program to Find nth Node From End of Linked List

In this tutorial, we will see how to find the nth node from the end of the linked list in java. LinkedList is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. Each element is known as a node. Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays. But before moving further, if you are not familiar with the concept of the linked list in java, then do check the article on Linked List in Java.

Input: Enter the Linked List elements: 6 7 8 4 5 1 3 2 5

Output: The 6th node from the end of the Linked List is: 4

This can be done by using the following methods:

Approach 1: Using the Length of the Linked List.

Approach 2: Using Two pointers concept.

Let us look at each of these approaches for a better understanding.

Program 1: Java Program to Find the nth Node From the End of LinkedList

In this program, we will see how to find the nth node from the end of the linked list in java by using the length of the linked list.

Algorithm:

1. Start
2. Create a linked list of string types using the linked list data structure.
3. Now add nodes to the linked list.
4. Call a user-defined function to calculate the nth node from the end of the linked list.
5. First, calculate the length of the linked list.
6. Now, print the (length – n + 1)th node from the beginning of the Linked List.
7. Stop

Let us look at the below example for a better understanding of the above algorithm.

//Java program to find nth node from end of linked list
public class LinkedList 
{
	Node head; 
	class Node 
	{
		int data;
		Node next;
		Node(int d)
		{
			data = d;
			next = null;
		}
	}
	void printNthFromEnd(int n)
	{
		int len = 0;
		Node temp = head;
	    while (temp != null) 
	    {
			temp = temp.next;
			len++;
		}
		if (len < n)
			return;
		temp = head;
		for (int i = 1; i < len - n + 1; i++)
			temp = temp.next;
		System.out.println(n+"th node from the end is "+temp.data);
	}
	public void add(int newData)
	{
		Node newNode = new Node(newData);
		newNode.next = head;
		head = newNode;
	}
	public static void main(String[] args)
	{
		LinkedList ll = new LinkedList();
		ll.add(12);
		ll.add(8);
		ll.add(21);
		ll.add(96);
        ll.add(52);
        ll.add(27);
        ll.add(14);
		ll.printNthFromEnd(6);
	}
}

6th node from the end is 27

Program 2: Java Program to Find the nth Node From the End of LinkedList

In this program, we will see how to find the nth node from the end of the linked list in java by using two pointers.

Algorithm:

1. Start
2. Create a linked list of string types using the linked list data structure.
3. Now add nodes to the linked list.
4. Call a user-defined function to calculate the nth node from the end of the linked list.
5. Declare two pointers: pointer1 and pointer2.
6. Initialize both the pointers to head.
7. First, move the first pointer to n nodes from the head.
8. Now move both pointers one by one until the reference pointer reaches the end.
9. Now the second pointer will point to the nth node from the end.
10. Return the second pointer.
11. Display the result.
12. Stop

Let us look at the below example for a better understanding of the above algorithm.

//Java program to find nth node from end of linked list
public class LinkedList 
{
	Node head; 
	class Node 
	{
		int data;
		Node next;
		Node(int d)
		{
			data = d;
			next = null;
		}
	}
	void printNthFromEnd(int n)
	{
	    Node ptr1 = head;
        Node ptr2 = head;
 
        int count = 0;
        if (head != null)
        {
            while (count < n)
            {
                if (ptr2 == null)
                {
                    System.out.println(n+ " is greater than the number of nodes in the list");
                    return;
                }
                ptr2 = ptr2.next;
                count++;
            }
 
            if(ptr2 == null)
            {
              head = head.next;
              if(head != null)
                System.out.println(n +"th node from the last is "+head.data);
            }
            else
            {
                   
              while (ptr2 != null)
              {
                  ptr1 = ptr1.next;
                  ptr2 = ptr2.next;
              }
              System.out.println(n +"th node from the last is "+ptr1.data);
            }
        }
	
	}
	public void add(int newData)
	{
		Node newNode = new Node(newData);
		newNode.next = head;
		head = newNode;
	}
	public static void main(String[] args)
	{
		LinkedList ll = new LinkedList();
		ll.add(12);
		ll.add(8);
		 ll.add(42);
        ll.add(29);
        ll.add(32);
		ll.add(87);
		ll.add(53);
		ll.printNthFromEnd(4);
	}
}

4th node from the last is 29