N'th node from the end of a Linked List

 

Need to find the N'th node from the end of Singly Linked List. Since its singly linked we can't traverse bidirectional and important condition is to traverse only once from start to end of the Linked List. Suppose if the length of Linked List is less than N then return -1.

Solution:
> Use 2 pointers where 1st pointer will be traversing from start to end and 2nd pointer will be starting when 1st pointer reaches N'th node.
> In such a way that when 1st pointer reaches the last node in Linked List 2nd pointer will be placed in the N'th node from last.

N'th node from the end of a Linked List


Let see simple Java code to implement LinkedList and to find the N'th node from last just by traversing only once.


public class FindLLNode {

 class LinkedList {
  int data;
  LinkedList next;

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

 public static void main(String[] args) {

  int val[] = new int[] { 23, 7, 10, 45, 9, 11 };

  int findNode = 3;

  FindLLNode obj = new FindLLNode();

  LinkedList start = obj.createLinkedList(val);

  int nthNodeVal = obj.findLLNode(start, findNode);

  System.out.println("nth Node Value from last : " + nthNodeVal);
 }

 private LinkedList createLinkedList(int[] val) {
  LinkedList start = null, temp = null;
  for (int i : val) {

   LinkedList node = new LinkedList(i);
   if (start == null) {
    start = temp = node;
   } else {
    temp.next = node;
    temp = temp.next;
   }
  }
  return start;
 }

 private int findLLNode(LinkedList start, int findNode) {

  LinkedList p1 = start, p2 = start;
  int i = 0;
  boolean flag = false;
  while (p1 != null) {
   if (i >= findNode) {
    p2 = p2.next;
    flag = true;
   }
   p1 = p1.next;
   i++;
  }
  if (!flag)
   return -1;
  return p2.data;
 }
}


OUTPUT:


3rd Node Value from last : 45

No comments:
Write comments