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