Question

/*Given the head of a linked list, find and return the kth node of the linked list

*Assume head is the first node

*If k is larger than the size of the linked list, return NULL

*

c++

* Example: n1 -> n2 -> n3 -> n4 -> n5, k = 3

* Return &n3

*/

Node* findKthNode(Node *head, int k){

return NULL;

//STUB: edit with the correct output, according to the lab instructions, using recursion

} must use recursive solutions

Answer 1

Explanation:-

just like the iterative function, we can implement recursive function by,

we have passed the head of the linked-list and number of the node to be found.

So for our recursive function, we can have,

if k<=0 then it's invalid k. we will return null.

else if head==null the also we will return null.

and if k==1 we will return head.

otherwise, we will return findKthNode(head,k-1)
so basically we are increasing head to head->next and decrease the k by 1.

so if the head is null and k is greater than one according to our condition we will return null.

Required Code:-

// Required recursive function to find kth node..
Node* findkthNode(Node* head, int k){
// If invalid k
if (k < 1)
return NULL;
// If linked list is empty
// Or if k is greater than linked-list size
if (head == NULL)
return NULL;
// Base case (start needs to be returned)
if (k == 1)
return head;
return findkthNode(head->next,k-1);
}

Screenshot of required code:-

Full code including driver function :-

#include<iostream>
using namespace std;

struct Node {
string data;
struct Node* next;
};

// Required recursive function to find kth node..
Node* findkthNode(Node* head, int k){
// If invalid k
if (k < 1)
return NULL;
// If linked list is empty
// Or if k is greater than linked-list size
if (head == NULL)
return NULL;
// Base case (start needs to be deleted)
if (k == 1)
return head;
return findkthNode(head->next,k-1);
}

/* Function to insert a node at the beginning */
void push(struct Node **head_ref,string new_data)
{
struct Node *new_node = new Node;
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}

/*Function to print a linked list */
void printLL(struct Node *head)
{
while (head!=NULL)
{
cout << head->data << " ";
head = head->next;
}
printf("\n");
}

/* Driver program*/
int main(){
struct Node *head = NULL;
/*I have just added function to
enter the data at beginning
So below 5 line create Linkedlist
of n1->n2->n3->n4->n5->n6*/
push(&head,"n6");
push(&head,"n5");
push(&head,"n4");
push(&head,"n3");
push(&head,"n2");
push(&head,"n1");

/*print current linked-list*/
cout<<"Current Link-list\n";
printLL(head);
/*node to be returned*/
cout<<"Enter the node number to find :";
int k;
cin>>k;
struct Node *kthNode = NULL;
kthNode = findkthNode(head,k);
if(kthNode!=NULL)
cout<<kthNode->data<<'\n';
else
cout<<"K is either negative or greater than linked-list size\n";

return 0;
}

Screenshot of Full Code:-

Output -1:-

Output 2:-

I hope you got the answer and got the logic behind it.
Please like and comment if you have any queries.