# Program to return nth node from the end in a linked list | faceprep

Program to find the nth node from the end in a linked list is discussed here. Given a linked list, the task is to find the Nth node from the end of the list and return it.

This problem can be solved in two different ways.

Method 1: By finding the length of the linked list, the Nth node from the end can be found easily.

Method 2: By using two pointers, the Nth node from the end can be found.

For example, consider the linked list given below.

Linked List : 1  -> 2 -> 3 -> 4 -> 5

4th node from the end is 2

## Algorithm to find the Nth node form the end (Using the length of the linked list)

• Input the number of nodes of the linked list.
• Input all the nodes and create the linked list.
• Input the Nth node to be returned from the end of the linked list.
• Find the length of the linked list.
• Return (length – N + 1)th node.

Program to return the Nth node from the end in a linked list is given below.

/* C program to return nth node from the end of a linked list */
#include
#include

/* Structure of node */
struct node
{
int data;
struct node *next;

void initialize()
{
}

/* Function to insert a node in linke dlist */
void insert(int num)
{
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = num;
}

/* Function to find the length of the linked list */
{
{
printf(“Error : Invalid node pointer !!!\n”);
return 0;
}

int length =0;
length++;
}
return length;
}

/* Function to find the Nth node from the last */
struct node* getNthLastNode(struct node* head, int n)
{
struct node *front, *back;
int i;
{
printf(“Error : n is greater than length of Linked List\n”);
return NULL;
}
for(i = 0; i < n-1; i++){
front = front->next;
}
/* Now, move both pointers together till front reaches
last node of linked list */
while(front->next != NULL){
front = front->next;
back = back->next;
}

return back;
}

/* Prints a linked list from head node till tail node */
while (nodePtr != NULL) {
printf(“%d”, nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf(“–>”);
}
}

int main()
{
int N, k;
struct node *NthNode;
initialize();
int new_node;
int i;
printf(“\nEnter the total number of nodes : “); /* Number of nodes */
scanf(“%d”,&k);
printf(“\nEnter the data for the nodes : “);
for(i = 0; i < k; i++)
{
scanf(“%d”,&new_node);
insert(new_node); /* Inserting the nodes */
}

printf(“\n\nEnter value of N : “);
scanf(“%d”, &N);
printf(“\nNth Last node is %d\n”, NthNode->data);
return 0;
}

/* C++ program to find nth node from the end of  a linked list */
#include
#include
using namespace std;

/* Structure of node */
struct node
{
int data;
struct node *next;

void initialize()
{
}

/* Function to insert a node in linke dlist */
void insert(int num)
{
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = num;
}

/* Function to find the length of the linked list */
{
{
cout << “\nError : Invalid node pointer !!!\n”;
return 0;
}

int length =0;
{
length++;
}
return length;
}

/* Function to find the Nth node from the last */
struct node* getNthLastNode(struct node* head, int n)
{
struct node *front, *back;
int i;
{
cout << “\nError : n is greater than length of Linked List\n”;
return NULL;
}
for(i = 0; i < n-1; i++)
{
front = front->next;
}
/* Now, move both pointers together till front reaches
last node of linked list */
while(front->next != NULL)
{
front = front->next;
back = back->next;
}

return back;
}

/* Prints a linked list from head node till tail node */
{
while (nodePtr != NULL)
{
cout << nodePtr->data << ” “;
nodePtr = nodePtr->next;
if(nodePtr != NULL)
cout << “–>”;
}
}

int main()
{
int N, k;
struct node *NthNode;
initialize();
int new_node;
int i;
cout << “\nEnter the total number of nodes : “; /* Number of nodes */
cin >> k;
cout << “\nEnter the data for the nodes : “;
for(i = 0; i < k; i++)
{
cin >> new_node;
insert(new_node); /* Inserting the nodes */
}

cout << “\nLinked List : “;
cout << “\n\nEnter value of N : “;
cin >> N;
cout << “\nNth Last node is ” << NthNode->data << endl;
return 0;
}

Time complexity: O(n)

## Algorithm to find the Nth node from the end (Using two pointers)

• Input the number of nodes of the linked list.
• Input all the nodes and create the linked list.
• Input the Nth node to be returned from the end of the linked list.
• Initialize both the reference pointer and the main pointer to the head node.
• First, move reference pointer to n nodes from the head node.
• Now, move both the pointers one by one until the reference pointer reaches the end of the list.
• Now, the main pointer will point to the nth node from the end.
• Return the main pointer.

Program to find the Nth node from the end of the linked list using two pointers is given below.

/* C program to return nth element from the end of a linked list */
#include
#include

/* Structure of node */
struct Node
{
int data;
struct Node *next;

void initialize()
{
}

/* Function to insert a node in linke dlist */
void insert(int num)
{
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = num;
}

void printNthFromLast(struct Node *head, int n)
{

int count = 0;
{
while( count < n )
{
if(ref_ptr == NULL)
{
printf(“%d is greater than the no. of “
“nodes in list”, n);
return;
}
ref_ptr = ref_ptr->next;
count++;
} /* End of while*/

while(ref_ptr != NULL)
{
main_ptr = main_ptr->next;
ref_ptr = ref_ptr->next;
}
printf(“\nNth node from the end : %d \n”, n, main_ptr->data);
}
}

/* Prints a linked list from head node till tail node */
while (nodePtr != NULL) {
printf(“%d”, nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf(“–>”);
}
}

int main()
{
int N, k;
struct node *NthNode;
initialize();
int new_node;
int i;
printf(“\nEnter the total number of nodes : “); /* Number of nodes */
scanf(“%d”,&k);
printf(“\nEnter the data for the nodes : “);
for(i = 0; i < k; i++)
{
scanf(“%d”,&new_node);
insert(new_node); /* Inserting the nodes */
}

printf(“\n\nEnter value of N : “);
scanf(“%d”, &N);
return 0;
}

/* C++ program to return nth node from the end in a linked list */
#include <iostream>
#include <stdlib.h>
using namespace std;

/* Structure of node */
struct Node
{
int data;
struct Node *next;

void initialize()
{
}

/* Function to insert a node in linke dlist */
void insert(int num)
{
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = num;
}

void printNthFromLast(struct Node *head, int n)
{

int count = 0;
{
while( count < n )
{
if(ref_ptr == NULL)
{
cout << n << ” is greater than the no. of nodes in list”;
return;
}
ref_ptr = ref_ptr->next;
count++;
}

while(ref_ptr != NULL)
{
main_ptr = main_ptr->next;
ref_ptr = ref_ptr->next;
}
cout << “\nNth node from the end : ” << main_ptr->data << endl;
}
}

/* Prints a linked list from head node till tail node */
{
while (nodePtr != NULL)
{
cout << nodePtr->data;
nodePtr = nodePtr->next;
if(nodePtr != NULL)
cout << “–>”;
}
}

int main()
{
int N, k;
struct node *NthNode;
initialize();
int new_node;
int i;
cout << “\nEnter the total number of nodes : “; /* Number of nodes */
cin >> k;
cout << “\nEnter the data for the nodes : “;
for(i = 0; i < k; i++)
{
cin >> new_node;
insert(new_node); /* Inserting the nodes */
}

cout << “\nLinked List : “; 