Chương trình C++ tìm nút giữa danh sách liên kết đơn bằng đệ quy

Cho danh sách liên kết, tìm nút giữa bằng đệ quy. Ví dụ [12, 14, 18, 36, 96, 25, 62] thì nút giữa là 36.

Giải pháp: đếm tổng số nút bằng đệ quy, lấy một nửa. Khi quay lại đệ quy, giảm n mỗi lần, trả về phần tử khi n=0.

Ví dụ mã nguồ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;
}

Kết quả đầu ra

Mid point is: 36