Find Nth node from last in a linked list
Lets understand what is the input and the expected output.
Find middle element of the Linked list
Algorithm
For finding N'th node from the end of a Linked List, below steps need to be performed.
STEP 1: Take 2 pointers, say ptrA and ptrB. initialize both pointers pointing at start node.
STEP 2: Move ptrB to Nth node from start keeping ptrA at start node.
STEP 3: If Nth position is not available that is, if ptrB encounters NULL before reaching Nth
position, then given Nth position is not available and is incorrect, so return -1.
If Nth position is valid input, then place ptr2 at Nth position.
STEP 4: Now, when both pointers are at N distance from each other, increment ptrA and ptrB one
node at a time until ptrB encounters NULL.
STEP 5: When ptrB reaches NULL, it means ptrA reached Nth position from last. So return node
at position ptrA.
Find Nth node from last in a linked list in Java.
package javabypatel.linkedlist.singly;
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));
//Print original list.
printLinkList();
//Print Nth last node.
System.out.println(getNthLastNodeFromLinkList(6));
}
// Solution 1
private int getNthLastNodeFromLinkList(int nodeFromLast) {
if(nodeFromLast<=0 || startNode==null){
return -1;
}
Node ptrA=startNode, ptrB = startNode;
//Moving ptrB N nodes from start keeping ptrA at head node.
for (int i=0; i < nodeFromLast; i++) {
//If ptrB reaches NULL, then return -1 as indication that given Nth value is incorrect and list doesn't contain N elements.
if(ptrB==null){
return -1;
}
ptrB = ptrB.getNext();
}
//Now incrementing ptrA and ptrB one node at a time until ptrB encounters NULL,
//when it encounters NULL then ptrA will be at Nth position from end of list.
while(ptrB!=null){
ptrB = ptrB.getNext();
ptrA = ptrA.getNext();
}
return ptrA.getData();
}
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;
}
}
}
package javabypatel.linkedlist.singly;
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;
}
}
Find Nth node from last in a linked list using single loop in Java.
package javabypatel.linkedlist.singly;
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));
//Print original list.
printLinkList();
//Print Nth last node.
System.out.println(getNthLastNodeFromLinkList(startNode, 6));
}
private int getNthLastNodeFromLinkList(Node startNode, int nthPosition) {
if(nthPosition<=0 || startNode==null){
return -1;
}
Node ptr1 = startNode;
//Incrementing ptr2 to nth position from start, keeping at head node until ptr2 reaches nth position.
//After ptr2 reaches nth position, both pointer will advance one node at a time until ptr2 reaches NULL.
//When ptr2 reaches NULL, ptr1 will be at Nth node away from last.
for(Node ptr2=startNode; ptr2!=null; ptr2 = ptr2.getNext()){
nthPosition--;
// ptr1 will only move when ptr2 reached nth position.
if(nthPosition<0){
ptr1 = ptr1.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 ptr1.
if(nthPosition<=0){
return ptr1.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;
}
}
}
Find Nth node from last in a linked list using Recursion.
package javabypatel.linkedlist.singly;
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();
int nthLastNodeData = getNthLastNodeFromLinkListRecursive(startNode, 5);
if(nthLastNodeData!=-1){
System.out.println("Nth last node is :"+nthLastNodeData);
}else{
System.out.println("Input out of linked list range.");
}
}
static int count;
private int getNthLastNodeFromLinkListRecursive(Node startNode, int nodeFromLast) {
if(startNode==null){
return -1;
}
//Recurse till last.
int data = getNthLastNodeFromLinkListRecursive(startNode.getNext(), nodeFromLast);
//count is static, so it will preserve state across recursive calls.
//Note: we started incrementing count after all recursive call,
//because we need Nth node from last, otherwise we would have increment count before recursive call for Nth node from start.
count++;
//when count value matched the nodeFromLast, we will return node value and from this point onwards,
//returned value is same across all up recursive calls.
if(count==nodeFromLast){
return startNode.getData();
}
return data;
}
private void printLinkList() {
Node tempNode1 = startNode;
while(tempNode1!=null){
System.out.print(tempNode1.getData() + " ");
tempNode1 = tempNode1.getNext();
}
System.out.println("\n============================================");
}
private void addNode(Node node) {
if(startNode!=null){
Node tempNode1 = startNode;
while(tempNode1.getNext()!=null){
tempNode1 = tempNode1.getNext();
}
tempNode1.setNext(node);
}else{
this.startNode = node;
}
}
}
There are ways to do without static variable, in this case, we need to return 2 states in each recursive call. So better to take array as return value.Two states that need to be returned in each recursive call is,
1. Current recursive call number to match against the Nth position.
2. Nth node data.
You may also like to see
Convert Sorted Linked List to balanced BST
Clone Linked list in Java
Sort Linked list in Java
Find Nth node from last in a linked list
Count zeros in a row wise and column wise sorted matrix
When to use interface and abstract class in Java? what is the difference between them?
Advanced Multithreading Interview Questions In Java
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment