विचार करें कि हमारे पास संख्याओं की एक सूची है; हमारा काम रिकर्सन का उपयोग करके लिंक की गई सूची के मध्य को ढूंढना है। तो अगर सूची के तत्व [12, 14, 18, 36, 96, 25, 62] हैं, तो मध्य तत्व 36 है।
इस समस्या को हल करने के लिए, हम सूची में नोड्स की कुल संख्या को पुनरावर्ती तरीके से गिनेंगे और इसका आधा हिस्सा करेंगे। फिर प्रत्येक कॉल में रिकर्सन डिक्रीमेंट एन बाय 1 के माध्यम से वापस रोलिंग, रिटर्न एलिमेंट जहां n शून्य है।
उदाहरण
#include<iostream>
#include<stack>
using namespace std;
class Node{
public:
int data;
Node *next;
};
Node* getNode(int data){
Node *newNode = new Node;
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void midpoint_task(Node* head, int* n, Node** mid){
if (head == NULL) {
*n /= 2;
return;
}
*n += 1;
midpoint_task(head->next, n, mid);
*n -= 1;
if (*n == 0) {
*mid = head;
}
}
Node* findMidpoint(Node* head) {
Node* mid = NULL;
int n = 1;
midpoint_task(head, &n, &mid);
return mid;
}
void append(struct Node** start, int key) {
Node* new_node = getNode(key);
Node *p = (*start);
if(p == NULL){
(*start) = new_node;
return;
}
while(p->next != NULL){
p = p->next;
}
p->next = new_node;
}
int main() {
Node *start = NULL;
int arr[] = {12, 14, 18, 36, 96, 25, 62};
int size = sizeof(arr)/sizeof(arr[0]);
for(int i = 0; i<size; i++){
append(&start, arr[i]);
}
Node* res = findMidpoint(start);
cout << "Mid point is: " << res->data;
} आउटपुट
Mid point is: 36