C -反向链表递归-不同函数签名

Question

有很多帖子可能有同样的问题，但问题说它必须由

完成

 node* reverseList (node * lh)
                              {
                               if(lh==NULL)............ ;
                                else if (lh->next==NULL)...........;
                                else ...........;
                              } 

必须填满这三个空格前两个是

return NULL 

和

return lh 

安排

一种方法可能只是向下并反转指针，但在这种情况下，我如何保持尾部完整，即使在回溯之后?这可能吗?

Answer 1

解决递归问题的诀窍是假装已经完成了。为了自己解决这个作业，你需要回答三个问题:

• 如何反转空列表?(即将lh设置为NULL的列表)?
• 如何反转只有一个项目的列表?
• 如果有人可以为你反转列表上的所有项目，除了最初的一个，你在哪里从初始列表中添加第一个项目到列表的预反转"尾部"部分?

你已经回答了前两个问题:NULL和lh是正确的答案。现在考虑第三个:

else {
    node *reversedTail = reverseList(lh->next);
    ...
}

此时，reversedTail包含列表的预反转尾部。您所需要做的就是将lh->设置为NULL旁边，将其添加到您持有的列表的后面，并返回reversedTail。最后的代码看起来像这样:

else {
    node *reversedTail = reverseList(lh->next);
    node *p = reversedTail; 
    while (p->next) p = p->next;
    p->next = lh;
    lh->next = NULL;
    return reversedTail;
}

Answer 2

我想这就是答案:

node *reverseList(node *lh)
{
    if (!lh) return NULL;
    else if (!lh->next) return lh;
    else {
        node *new_head = reverseList(lh->next);
        lh->next->next = lh;
        lh->next = NULL;
        return new_head;
    }
}

返回反向链表的头，即原链表的尾部。

head = reverse_list(head);

Answer 3

下面是一个API，它完成了单个链表的反转，这是我见过的最好的算法之一:

void iterative_reverse() 
{ 
    mynode *p, *q, *r; 
    if(head == (mynode *)0) 
    { return; 
    } 
    p = head; 
    q = p->next; 
    p->next = (mynode *)0; 
    while (q != (mynode *)0) 
    { 
        r = q->next; 
        q->next = p; 
        p = q; 
        q = r; 
    } 
    head = p; 
 }