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; } } }
Questions on Stack, Queues, Linkedlist, Binary Trees, Sorting, Searching, Graphs etc with solution using Java Language.
Sunday, 24 May 2015
How to find nth element from the end of a singly linked list
Labels:
Linkedlist
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment