Home » Interview Questions » LinkedList Interview Questions » Find nth node of the Linked list from the end

Find nth node of the Linked list from the end


()

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

READ  Swap kth node from beginning with kth node from end

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions