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

void initialize()
{
head = NULL;
}

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

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

int length =0;
while(head != NULL){
head = head->next;
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;
front = back = head;
if(n > getLength(head))
{
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 */
void printLinkedList(struct node *nodePtr) {
while (nodePtr != NULL) {
printf(“%d”, nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf(“–>”);
}
}

int main()
{
int N, k;
struct node *NthNode;
initialize();
/* Creating a linked List*/
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(“\nLinked List : “);
printLinkedList(head);
printf(“\n\nEnter value of N : “);
scanf(“%d”, &N);
NthNode = getNthLastNode(head, 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;
} *head;

void initialize()
{
head = NULL;
}

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

/* Function to find the length of the linked list */
int getLength(struct node *head)
{
if (head == NULL)
{
cout << “\nError : Invalid node pointer !!!\n”;
return 0;
}

int length =0;
while(head != NULL)
{
head = head->next;
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;
front = back = head;
if(n > getLength(head))
{
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 */
void printLinkedList(struct node *nodePtr)
{
while (nodePtr != NULL)
{
cout << nodePtr->data << ” “;
nodePtr = nodePtr->next;
if(nodePtr != NULL)
cout << “–>”;
}
}

int main()
{
int N, k;
struct node *NthNode;
initialize();
/* Creating a linked List*/
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 : “;
printLinkedList(head);
cout << “\n\nEnter value of N : “;
cin >> N;
NthNode = getNthLastNode(head, 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;
} *head;

void initialize()
{
head = NULL;
}

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

void printNthFromLast(struct Node *head, int n)
{
struct Node *main_ptr = head;
struct Node *ref_ptr = head;

int count = 0;
if(head != NULL)
{
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 */
void printLinkedList(struct Node *nodePtr) {
while (nodePtr != NULL) {
printf(“%d”, nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf(“–>”);
}
}

int main()
{
int N, k;
struct node *NthNode;
initialize();
/* Creating a linked List*/
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(“\nLinked List : “);
printLinkedList(head);
printf(“\n\nEnter value of N : “);
scanf(“%d”, &N);
printNthFromLast(head, 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;
} *head;

void initialize()
{
head = NULL;
}

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

void printNthFromLast(struct Node *head, int n)
{
struct Node *main_ptr = head;
struct Node *ref_ptr = head;

int count = 0;
if(head != NULL)
{
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 */
void printLinkedList(struct Node *nodePtr)
{
while (nodePtr != NULL)
{
cout << nodePtr->data;
nodePtr = nodePtr->next;
if(nodePtr != NULL)
cout << “–>”;
}
}

int main()
{
int N, k;
struct node *NthNode;
initialize();
/* Creating a linked List*/
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 : “;
printLinkedList(head);
cout << “\n\nEnter value of N : “;
cin >> N;
printNthFromLast(head, N);
return 0;
}