재귀를 사용하여 링크 된 목록을 역전하는 문제

Question

재귀 함수를 호출하는 드라이버 함수를 작성해야합니다. 나는 내가 운전자 기능에서 무엇을해야하는지 궁금해하고 있었다.

이 프로그램은 연결된 목록을 역전합니다.

void invert_r() 
{ 
    //This is the driver function for recursive_invert 

    nodeType<Type> *p, *q; 

    q = first; 
    p = first; 
    recursive_invert(q, p); 
} 
nodeType<Type>* recursive_invert(nodeType<Type> *q, nodeType<Type> *p) 
{ 
    //Invert a linked list using recursion. 
    //DO NOT create any new node in your implementation 
    if(p -> link == NULL) 
    { 
     q -> link = p; 
     return p; 
    } 
    else 
    { 
     recursive_invert(p -> link, q) -> link = p; 
    } 
    return p; 
} 

Answer 1

void recursiveReverse(struct node** head_ref) 
{ 
    struct node* first; 
    struct node* rest; 

    /* empty list */ 
    if (*head_ref == NULL) 
     return; 

    /* suppose first = {1, 2, 3}, rest = {2, 3} */ 
    first = *head_ref; 
    rest = first->next; 

    /* List has only one node */ 
    if (rest == NULL) 
     return; 

    /* reverse the rest list and put the first element at the end */ 
    recursiveReverse(&rest); 
    first->next->next = first; 

    /* tricky step -- see the diagram */ 
    first->next = NULL;   

    /* fix the head pointer */ 
    *head_ref = rest;    
}