Hãy xem xét chúng ta có một danh sách các số; nhiệm vụ của chúng ta là tìm giữa danh sách được liên kết bằng cách sử dụng đệ quy. Vì vậy, nếu các phần tử trong danh sách là [12, 14, 18, 36, 96, 25, 62], thì phần tử ở giữa là 36.
Để giải quyết vấn đề này, chúng tôi sẽ đếm tổng số nút trong danh sách theo cách đệ quy và thực hiện một nửa điều này. Sau đó, quay trở lại thông qua giảm đệ quy n đi 1 trong mỗi lần gọi, trả về phần tử với n bằng không.
Ví dụ
#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;
} Đầu ra
Mid point is: 36