Find the nth node from the end of a Linked List
Find the nth node from the end of a Linked List
In this problem, we have given a singly linked list and a number 'n,' and we need to find the nth node from the end of the linked list and return it.
Example:
List:
13 -> 16 -> 9 -> 10 -> 4 -> 6 -> 1 -> 3, n = 3
Output:
6
Method 1: Using length of linked list
- Firstly, we need to find the length of linked list.
- Then, we will print the (length – n +1)th node from the beginning of the linked list.
Source code to implement this method using C programming:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node * next;
};
struct node * start = NULL; int len=0, n;
// For inserting the elements in the linked list
void add(int item)
{
struct node * t, * p;
t = (struct node * )malloc( sizeof( struct node ));
if(start == NULL)
{
start = t;
start -> info = item;
start -> next = NULL;
return;
}
else
{
struct node * p = start;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// For finding the length of the linked list
void length(struct node * temp)
{
while(temp != NULL)
{
len += 1;
temp = temp -> next;
}
}
// For finding the nth node from the end of a Linked List
struct node * findNode(struct node * temp)
{
int i;
length(temp);
int j = (len - n + 1);
for(i = 0; i < j-1; i++)
{
temp = temp -> next;
}
return temp;
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
printf(" Linked list is empty\n");
}
while(t -> next != NULL)
{
printf("%d -> ", t -> info);
t = t -> next;
}
printf("%d\n", t -> info);
}
// Driver Function
int main()
{
int i;
printf("which node you want to search from last:");
scanf("%d", &n);
for (i = 2; i < 12; i+=2)
{
add(i);
}
printf("Linked List is:");
traverse(start);
printf("node is:%d", findNode(start) -> info);
return 0;
}
Output:
Time Complexity: The time complexity of the above method is O(n).
Method 2: Using two pointers
In this method, we will maintain two pointers – the first is the reference pointer, and the second is the main pointer. Next, we will initialize both reference and main pointers to the starting address of the linked list. Next, we will first move the reference pointer to n nodes from the head and then move both pointers one by one until the reference pointer reaches the end. Now, the main pointer will point to the nth node from the end. Finally, it will return the main pointer.
Source code to implement this method using C programming:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *next;
};
struct node *start = NULL; int len = 0, n;
// For inserting the elements in the linked list
void add(int item)
{
struct node * t, * p;
t = (struct node * )malloc( sizeof( struct node ));
if(start == NULL)
{
start = t;
start -> info = item;
start -> next = NULL;
return;
}
else
{
struct node * p = start;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// For finding the nth node from the end of a Linked List
void nodeFromLast(struct node * temp)
{
struct node * main_ptr = temp;
struct node * ref_ptr = temp;
int count = 0;
if(temp != 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++;
}
if(ref_ptr == NULL)
{
temp = temp -> next;
if(temp != NULL)
printf("Node no. %d from last is %d ", n, main_ptr -> info);
}
else
{
while(ref_ptr != NULL)
{
main_ptr = main_ptr -> next;
ref_ptr = ref_ptr -> next;
}
printf("Node no. %d from last is %d ", n, main_ptr -> info);
}
}
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
printf(" Linked list is empty\n");
}
while(t -> next != NULL)
{
printf("%d -> ", t -> info);
t = t -> next;
}
printf("%d\n", t -> info);
}
// Driver Function
int main()
{
int i;
printf("which node you want to search from last: ");
scanf("%d", &n);
for (i = 2; i < 12; i+=2)
{
add(i);
}
printf("Linked List is:");
traverse(start);
nodeFromLast(start);
return 0;
}
Output:
Time Complexity: The time complexity of the above method is O(n).