Find value of Nth node of a linked list

Given a linked list, write a function that takes the linked list and the integer index and returns the value stored in the node at that index position

Example

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

Output : 15

Here, 15 data value is at the 3 rd index of the linked list

Time Complexity : O(n)

Algorithm

1. Take a variable named count and initilize it to 0 and create a pointer named temp and point it to head of the linked list .
2. Till the end of the linked list ie, temp!= Null
    a. If count is equal to the input index, then return the current node of the linked list else,
    b. Increament the count value and move the temp pointer one step ahead. ie, temp = temp->next.

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
Scroll to Top