Wednesday, November 13, 2019

Find Nth Node From The End Of Linked List

```

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.

// Print Nth last node.
System.out
}

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;
}

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
```