使用递归反转链表时出现问题

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