## Given a linked list, write a program for finding the nth element from the end of the linked list

### Example

Input: 6->16->15->50->1->23->49, N= 3

**Output :** 1

Here, the 3rd element from the end is 1

**Time Complexity : O(n),**

where n is the length of the linked list.

## Algorithm

This is one of the method to find the nth element from the end of a Linked List

1. Create two pointers first, second and initialize them to the head of the linked list

2. Move the second pointer N steps

3. Till second->next not equal to Null, move first and second pointer one step ahead.

4. first is the nth element from the end.

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
struct LL{
int data;
LL *next;
};
void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
struct LL* curr=new LL;
curr->data=dataToBeInserted;
curr->next=NULL;
if(*head==NULL)
*head=curr; //if this is first node make this as head of list
else
{
curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
*head=curr;
}
//O(1) constant time
}
struct LL* nthNodeFromEnd(struct LL**head,int n)
{
struct LL*first=*head , *second = *head;
for(int i=1;i<n;i++) // increase second pointer ahead by n steps
{
if(second)
second=second->next;
else
break;
}
if(second == NULL)
{
cout<<"List has less than specified number of nodes\n";
return NULL;
}
while(second->next!=NULL) //increase by one steps now till we reach the last node and now the first will point to Nth from end
{
first = first->next;
second = second->next;
}
return first;
}
void display(struct LL**head)
{
struct LL*temp=*head;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
int main()
{
struct LL *head = NULL; //initial list has no elements
insertAtBeginning(&head,6);
insertAtBeginning(&head,16);
insertAtBeginning(&head,15);
insertAtBeginning(&head,50);
insertAtBeginning(&head,1);
insertAtBeginning(&head,23);
display(&head);
int N = 3; //number of node whose value is to be known
struct LL * NthFromEnd = nthNodeFromEnd(&head,N);
if(NthFromEnd == NULL)
{ }
else
cout<<N<<" th node from end is "<<NthFromEnd->data<<endl;
return 0;
}
```

Try It

**Next >**
**< Prev**