โปรแกรม C++ หาจุดกึ่งกลางของ Singly Linked List แบบ Recursive

พิจารณาว่าเรามีรายการตัวเลข งานของเราคือหาจุดกึ่งกลางของ linked list โดยใช้การเรียกซ้ำ (recursion) ถ้าสมาชิกในรายการคือ [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

ผลลัพธ์
Mid point is: 36