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->next 设置为 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;
}