C++에서 재귀적으로 단일 연결 목록의 중간 찾기

숫자 목록이 있다고 가정해 보겠습니다. 우리의 작업은 재귀를 사용하여 연결 목록의 중간을 찾는 것입니다. 따라서 목록 요소가 [12, 14, 18, 36, 96, 25, 62]이면 중간 요소는 36입니다.

이 문제를 해결하기 위해 목록의 총 노드 수를 재귀적으로 계산하고 이의 절반을 수행합니다. 그런 다음 각 호출에서 n만큼 감소하는 재귀를 통해 롤백하고 n이 0인 요소를 반환합니다.

예시

#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