c++ - 使用递归反转链表的问题

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