This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Sunday, 24 May 2015

How to find nth element from the end of a singly linked list


package linkedlist.singly;

//How would you find the nth to last element in a linked list?
//Say find 3rd last element of linklist.
//If we keep a gap of 3 Nodes between p1 and p2 and then start incrementing both p1 and p2 one by one until p2 which is 3 element ahead of p1 is null. now when p2 is null, then p1 will be at 3rd last position.
//this says, keep p1 and p2 at node 1 initially. then move p2 to n(n=3 in our case) location ahead. if p2 becomes null in between moving it to 3 positions ahead 
//then we will not able to find nth last element in linklist as it doen't contain that much element.
//otherwise, once p2 advanced to 3 locations ahead, now start iterating one by one until p2 reaches null, when p2 reaches null, p1 will be at 3rd last position.
public class GetNthLastElementFromList {

 Node startNode;
 public static void main(String[] args) {
  new GetNthLastElementFromList();
 }
 
 public GetNthLastElementFromList() {
  
  addNode(new Node(10));
  addNode(new Node(20));
  addNode(new Node(30));
  addNode(new Node(40));
  addNode(new Node(50));
  addNode(new Node(60));
  addNode(new Node(70));

  printLinkList();
  System.out.println(getNthElementSolution1(7));
  //System.out.println(getNthElementSolution2(startNode, 1));  
 }

 // Solution 1
 private int getNthElementSolution1(int nodeFromLast) {

  if(nodeFromLast<=0 || startNode==null){
   return -1;
  }

  Node temp1= startNode, temp2 = startNode;

  for (int i=0; i < nodeFromLast; i++) {
   if(temp2==null){
    return -1;
   }
   temp2 = temp2.getNext();
  }

  while(temp2!=null){
   temp2= temp2.getNext();
   temp1=temp1.getNext();
  }

  return temp1.getData();  
 }

 // Solution 2 : it uses single for loop.
 private static int getNthElementSolution2(Node startNode, int nth) {
  Node temp1=startNode, temp2 = startNode;
  int count=0;
  for(;temp1!=null;){
   count++;
   if(nth-count<0){
    temp2 = temp2.getNext();
   }
   temp1 = temp1.getNext();
  }
  
  if(count>=nth){
   return temp2.getData();
  }
  return -1;
 }

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

 private void addNode(Node node) {
  if(startNode!=null){
   Node tempNode = startNode;
   while(tempNode.getNext()!=null){
    tempNode = tempNode.getNext();
   }
   tempNode.setNext(node);
  }else{
   this.startNode = node;
  }
 }
}



No comments:

Post a Comment