พิจารณาว่าเรามีรายการตัวเลข งานของเราคือค้นหาตรงกลางของรายการที่เชื่อมโยงโดยใช้การเรียกซ้ำ ดังนั้นหากองค์ประกอบรายการคือ [12, 14, 18, 36, 96, 25, 62] ดังนั้นองค์ประกอบกลางคือ 36
เพื่อแก้ปัญหานี้ เราจะนับจำนวนโหนดทั้งหมดในรายการในลักษณะแบบเรียกซ้ำ และดำเนินการครึ่งหนึ่ง จากนั้นย้อนกลับผ่านการลดการเรียกซ้ำ n ทีละ 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
