使用遞歸來反轉鏈表的問題

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;    
}