Wednesday, November 13, 2019

Find Nth Node From The End Of Linked List


package linkelist.example;

public class Node {

 private int data;
 private Node next;

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

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getNext() {
  return next;
 }

 public void setNext(Node next) {
  this.next = next;
 }
}
package linkelist.example;

public class GetNthLastElementFromList {

 Node startNode;

 public static void main(String[] args) {
  GetNthLastElementFromList getNthLastElementFromList = new GetNthLastElementFromList();

  Node n1 = new Node(10);
  Node n2 = new Node(20);
  Node n3 = new Node(30);
  Node n4 = new Node(40);
  Node n5 = new Node(50);
  Node n6 = new Node(60);
  Node n7 = new Node(70);
  Node n8 = new Node(80);

  getNthLastElementFromList.startNode = n1;

  n1.setNext(n2);
  n2.setNext(n3);
  n3.setNext(n4);
  n4.setNext(n5);
  n5.setNext(n6);
  n6.setNext(n7);
  n7.setNext(n8);

  // Print original list.
  getNthLastElementFromList.printLinkList();

  // Print Nth last node.
  System.out
    .println(getNthLastElementFromList.getNthLastNodeFromLinkList(getNthLastElementFromList.startNode, 3));
 }

 private int getNthLastNodeFromLinkList(Node startNode, int nthPosition) {
  if (nthPosition <= 0 || startNode == null) {
   return -1;
  }

  Node slowPointer = startNode;

  // Incrementing fastPointer to nth position from start, keeping at head node
  // until fastPointer
  // reaches nth position.
  // After fastPointer reaches nth position, both pointer will advance one node at
  // a time
  // until fastPointer reaches NULL.
  // When fastPointer reaches NULL, slowPointer will be at Nth node away from
  // last.
  for (Node fastPointer = startNode; fastPointer != null; fastPointer = fastPointer.getNext()) {
   nthPosition--;

   // slowPointer will only move when fastPointer reached nth position.
   if (nthPosition < 0) {
    slowPointer = slowPointer.getNext();
   }
  }

  // If nthPosition is greater than 0, it means nthPosition is larger than the
  // number of nodes
  // present and such position doesn't exist, so return -1 in that case else
  // return data pointed by slowPointer.
  if (nthPosition <= 0) {
   return slowPointer.getData();
  }

  return -1;
 }

 private void printLinkList() {
  Node tempNode = startNode;
  while (tempNode != null) {
   System.out.print(tempNode.getData() + " ");
   tempNode = tempNode.getNext();
  }
  System.out.println("\n=============");
 }

}
Output:

10 20 30 40 50 60 70 80 
=============
60

No comments:

Post a Comment