Find nth node from end / last node in a single linked list in java (example)

• Give a single linked list, find nth node from end in a single linked list.
  • Traverse the single linked using non recursive or iterative algorithm.
• The n can be any arbitrary number within the range of number of nodes in linked list.
• We have discussed the similar algorithm to find the middle or mid node in a single linked list.

• The head is pointing to first node of single linked list
  • Single linked list is terminated at node 50.
•  The Node 50 is supposed to situated at distance 1 from last (assuming that next node is at null).
• If we start looking at the linked list from last then Node 40 should be situated at the n = 2 and same apply for rest of nodes.
  • Fig 2 shows the indexes of node wrt to last node in a single linked list.

Example – find n = 3 node from end of single linked list in java.
Step 1:  

• Created two variable slow and fast reference
• slow and fast reference will point to head of single linked list.
• slow reference will jump one node.
• fast reference will initially move by n = 3 nodes.
  • As we are looking for n = 3rd node from end of single linked list
  • then fast reference will move one by one.

Step 2:

• fast reference will initially moved by n = 3
• fast will start pointing to Node 40.

Step 3:

• slow reference will jump one by one
• fast reference will jump one by one

Step 4: 

• fast reference reached end of linked list
  • Our iteration will complete
• slow reference will give the node we are looking for
  • slow is pointing to node which is 3rd from last of linked list

Time complexity of algorithm is O(n).

Find nth element from end of single linked list (non recursive algorithm)

1.) FindNthNodeFromLast Class:

• We are passing the head of single linked list to findNthNodeFromLast.
• We will get nth node from end of single linked list.

package org.learn.Question;

import org.learn.List.Node;

public class FindNthNodeFromLast {
	public static Node findNthNodeFromLast(Node head, int n) {
		if (null == head) {
			System.out.println("Single linked list is empty");
			return null;
		}

		Node slow = head;
		Node fast = head;
		int index = 0;
		while (index++ < n) {
			if (null == fast) {
				System.out.printf("\nn=%d is larger than length of linked list", n);
				return null;
			}
			fast = fast.next;
		}
		while (fast != null) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}

	public static void insert(Node head, int data) {
		while (head.next != null)
			head = head.next;
		head.next = new Node(data);
	}

	public static void print(Node head) {
		while (head != null) {
			System.out.printf("%d ", head.data);
			head = head.next;
		}
		System.out.println("");
	}
}

2.) App Class:

We are performing the following operation in main method.

• We are creating single linked list in main method
• We will find out node from last for n = 1,3 and 5 in single linked list

package org.learn.Client;

import org.learn.List.Node;
import org.learn.Question.FindNthNodeFromLast;

public class App {
	public static void main(String[] args) {
		int[] data = { 10, 20, 30, 40, 50 };
		Node head = new Node(data[0]);
		for (int count = 1; count < data.length; count++)
			FindNthNodeFromLast.insert(head, data[count]);
		System.out.printf("1. Single linked list is : ");
		FindNthNodeFromLast.print(head);

		int n = 1;
		Node nodeFromLast = FindNthNodeFromLast.findNthNodeFromLast(head, n);
		if (null != nodeFromLast) {
			System.out.printf("2. Node from last for n = %d is %d", n, nodeFromLast.data);
		}

		n = 3;
		nodeFromLast = FindNthNodeFromLast.findNthNodeFromLast(head, n);
		if (null != nodeFromLast) {
			System.out.printf("\n3. Node from last for n = %d is %d", n, nodeFromLast.data);
		}

		n = 5;
		nodeFromLast = FindNthNodeFromLast.findNthNodeFromLast(head, n);
		if (null != nodeFromLast) {
			System.out.printf("\n4. Node from last for n = %d is %d", n, nodeFromLast.data);
		}
	}
}

3.) Node Class:

• Node Class representing the node (s) of single linked list.

package org.learn.List;

public class Node {
	public int data;
	public Node next;

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

Output – find nth node from end of single linked list in java

1. Single linked list is : 10 20 30 40 50 
2. Node from last for n = 1 is 50
3. Node from last for n = 3 is 30
4. Node from last for n = 5 is 10

Download Code – find nth node from end of single linked list