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