## 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; }