Introduction
The nodes of the singly linked list contain two important pieces of information—first, the value they hold, and second, the pointer to the next node. The second property forms the basis for the traversal of a singly linked list.
Still, the disadvantage of having such an architecture is that we can not randomly access any node, and to reach a node, we have to traverse all the nodes before it.
If we want to access the Nth node from last, the task becomes even more difficult. Since we can’t access the nodes randomly, we need to find other ways to do this. We will start with the basic approach of counting the number of nodes in the list, then accessing the Nth node from last.
Then we will move to an advanced approach known as the two pointer approach.
Approach using the length of the list
Let’s say you have a singly linked list, and you need to find the value at the 3rd last node in it. You will traverse the linked list till the last node, thus finding its length. Then you will traverse back to the 3rd, the last node from the end.
This method takes the list’s head pointer and then traverses the list until we encounter a node with the next pointer pointing to a null pointer. We then store the numbers of nodes traversed, which denote the length of the linked list. Then we traverse back to the nth node from the last node.
Algorithm:
- Construct, or take a linked list from the input.
- Declare a length variable.
- Traverse the linked list using a loop to find the length by incrementing the length variable for each node traversed.
- Again traverse the linked list and Return (length – N + 1)th node from the head.
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
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.
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.
The last node of the linked list contains the null pointer as the pointer to the next node.
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.
The Circular Linked list has this characteristic: its last node contains the pointer to the head as its next pointer. You can read more about the different types of the linked list here.
Key takeaways
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.
To read more about the linked list and the operations on it, visit here. You can also practice similar problems on CodeStudio. If you liked this blog, share it with your friends!
