Implementation of the First Method
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *next;
};
// Function to find the nth node from last.
void nthnodefromlast(struct node* head, int n)
{
int l=0;
struct node* var =head;
// Counting the number of nodes.
while(var!=nullptr)
{
var=var->next;
l++;
}
// To check if n is smaller than the length we calculated.
if(l<n)
{
cout<<n<<" is greater than no. of nodes in the list";
return;
}
var= head;
// To get the nth node from last, i.e. (l-n+1)th node from the head.
for(int i=0;i<l-n;i++)
{
var=var->next;
}
cout<<"Node no. "<<n<<" from last is "<<var->data;
return;
}
// Function to push elements into the list.
void push(struct node** headr, int new_val)
{
// Creatng a new node.
struct node* new_node= new node();
// Putting the value in the node.
new_node->data= new_val;
// Linking the node to the list.
new_node->next=(*headr);
// Shifting the head pointer to the new node.
*headr= new_node;
}
// Driver function.
int main()
{
// Creating an empty list.
struct node* head=nullptr;
// Enter no of elements in the node.
int size;
cin>>size;
// Pushing the elements in it.
for(int i=0;i<size;i++)
{
int a;
cin>>a;
push(&head,a);
}
// Enter the node to be returned from the last node.
int n;
cin>>n;
// Function call for nth node from last.
nthnodefromlast(head,n);
return 0;
}
Input-
6
5 8 10 4 6 3
2
Output-
Node no. 2 from last is 8
The time complexity of this approach is O(N).
The space complexity of this approach is O(1).
Two Pointer Method
This method helps us access the nth node from last more efficiently than the previous method. It involves the idea of using two pointer n nodes apart, and then they are moved until the pointer moving ahead reaches the last node, then we access the node pointed by the second pointer, which is n nodes away from the pointer at the last node.
To put the above process in simple words-
-
We take two-pointer variables, namely the main pointer and reference pointer, both pointing to the head of the linked list.
-
Then we move the reference pointer to the nth node in the linked list. From here, we start moving both the pointers simultaneously. If the reference pointer is moved ahead by one node, the main pointer also moves one point ahead.
- It continues till the reference pointer reaches the tail of the linked list. Now, we access the node pointed by the main pointer, and since it is n nodes behind the reference node, it is the nth node from the last node of the linked list.
Algorithm:
-
Construct, or take a linked list from the input.
-
Declare two pointers, one as the main pointer and the other as the reference pointer. Initialize both of them to the head node.
-
Now, move the reference pointer n nodes from the head node.
-
From here, move both pointers one by one simultaneously until the reference pointer reaches the last node.
-
The node pointed by the main pointer is the nth node from last.
- Return the main pointer.
Implementation of Two-Pointer Method
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *next;
};
// Function to find the nth node from last.
void nthnodefromlast(struct node* head, int n)
{
// Initialising both the pointers with head.
struct node *mainp=head;
struct node *refp=head;
int count=0;
if(head!=nullptr)
{
while(count<n)
{
if(refp==nullptr)
{
cout<<n<<" is greater than no. of nodes in the list";
return;
}
refp=refp->next;
count++;
}
if(refp==nullptr)
{
// When the reference pointer reaches the last node.
head=head->next;
if(head!=nullptr)
{
cout<<"Node no. "<<n<<"from last is "<<mainp->data;
}
}
else
{
// Moving both the pointer one node ahead each time.
while(refp!=nullptr)
{
mainp=mainp->next;
refp=refp->next;;
}
cout<<"Node no. "<<n<<" from last is "<<mainp->data;
}
}
}
// Function to push elements into the list.
void push(struct node** headr, int new_val)
{
// Creatng a new node.
struct node* new_node= new node();
// Putting the value in the node.
new_node->data= new_val;
// Linking the node to the list.
new_node->next=(*headr);
// Shifting the head pointer to the new node.
*headr= new_node;
}
// Driver function.
int main()
{
// Creating an empty list.
struct node* head=nullptr;
// Enter no of elements in the node.
int size;
cin>>size;
// Pushing the elements in it.
for(int i=0;i<size;i++)
{
int a;
cin>>a;
push(&head,a);
}
// Enter the node to be returned from the last node.
int n;
cin>>n;
// Function call for nth node from last.
nthnodefromlast(head,n);
return 0;
}
Input-
6
5 8 10 4 6 3
2
Output-
Node no. 2 from last is 8
The time complexity of this approach is O(N).
The space complexity of this approach is O(1).
Frequently Asked Questions
How would you find the Nth node of a linked list from the end?
There are two main methods to do that, either you can find the nth node from the last using the length of the linked list or using the two-pointer method.
What is the Nth node in the linked list?
If we start traversing the linked list from the head, with the help of the next pointer in each node, the nth node we access in this manner is the nth node in the linked list.
In which linked list is the last node address null?
The last node of the linked list contains the null pointer as the pointer to the next node.
What does a linked list node include?
There are two major parts of the node of a singly linked list, i.e., the value it holds and a pointer to the next node.
Which linked list will point to the first node from the last node?
The Circular Linked list has this characteristic: its last node contains the pointer to the head as its next pointer.
Conclusion
In this blog, we explored finding the nth node from last in a linked list. We used the following methods for it-
- The first method was to traverse the linked list, find its length, then use its length, find the nth node from last, then traverse to access that.
-
The second method was the two-pointer method. In it, we maintain two pointers known as a reference and main pointer. The reference pointer moves n nodes away from the main pointer at the head. Then both of them start traversing the list simultaneously, one node at a time, until the reference pointer reaches the last node. Now, the node by the main pointer is the nth node from the last.
Recommended Problems -
You can practice similar problems on Coding Ninjas Studio. If you liked this blog, share it with your friends!