In the given linked list find nth node. The function should return the data value in the nth node. n is input integer index.
Example
Time complexity : O(n)
Algorithm
1. Initialize count equal to 0.
2. Traverse in the linked list.
a. If count is equal to the input index then return current node data.
b. Increment count.
c. Move forward position. (continue traversing)
C++ Program
#include <bits/stdc++.h>
using namespace std;
struct LLNode
{
int data;
struct LLNode* next;
};
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
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 curr (new) node's next point to head and make this new node a the head
*head=curr;
}
//O(1) constant time
}
//display linked list
void display(struct LLNode**node)
{
struct LLNode *temp= *node;
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 PrintNth(struct LLNode* head, int index)
{
struct LLNode* current = head;
int count = 0;
//Start travesing from head.
while (current != NULL)
{
if(count == index)
{
return (current->data);
}
count++;
current = current->next;
}
return 0;
}
//Main function
int main()
{
struct LLNode* head = NULL;//Initial list has no elements
insertAtBeginning(&head, 9);
insertAtBeginning(&head, 8);
insertAtBeginning(&head, 7);
insertAtBeginning(&head, 6);
insertAtBeginning(&head, 5);
insertAtBeginning(&head, 4);
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 1);
cout<<"Input linked list is: ";
display(&head);
int k;
cout<<"Enter index: ";
cin>>k;
cout<<"Node at index "<< k <<" is: "<<PrintNth(head,k);
return 0;
}
