1

我无法弄清楚如何让函数递归地返回新列表的“头”。它们附加得很好，但递归地我无法弄清楚如何“保存我的位置”可以这么说。

struct node {
    int value;
    node *next;
};

node* append(node *&L1, node *L2)
{
    if(L1->next == NULL) {
        L1->next = L2;
        return L1;
    }
    else if(L2 == NULL) 
       return L1;
    else 
       return append(L1->next, L2);
}
void main()
{
    node *a, *b, *c, *d;
    a=new node;
    b=new node;
    c=new node;
    d=new node;
    a->value = 4;
    a->next = b;
    b->next = NULL;
    b->value = 7;
    c->next = d;
    c->value = 12;
    d->next = NULL;
    d->value = 8;
    append(a,c);
}
4

3 回答 3

1

递归函数几乎总是有两个组成部分：基本情况和递归情况。因此，您必须首先考虑您的要求是什么？

例如，假设你有两个链表：listA & listB：

  1. 基本情况：当 listA 没有更多元素时，停止
  2. 递归案例：分离 listA 的最后一个元素，将其附加到 listB 的开头。再次递归调用函数

从上面的伪代码你应该有足够的东西开始编程

于 2013-01-29T04:03:21.053 回答
1 
node* append(node *&L1, node *L2)
{
   if (L1 == NULL)
       L1 = L2;
   else if (L1->next != NULL)
       append(L1->next, L2);
   else
       L1->next = L2;

   // Return the head node of the linked list
   return L1;
}
于 2013-01-29T04:17:50.510 回答
1

除其他事项外，您需要考虑 L1 在开始时为 NULL。值得庆幸的是，考虑到它也考虑了实际的附加。

node *append(node *&L1, node* L2)
{
    if (!L1)
        L1 = L2;
    else
        append(L1->next, L2);
    return L1;
}

这个怎么运作

小事例(L1 = NULL, L2 = <anything>>)

  1. 输入函数；L1 = NULL和L2 = <<anything>>
  2. if(!L1)很满意。我们分配L2给L1，然后返回L1。

普通案例：(L1 != NULL, L2 = <anything>>)

  1. 输入函数；L1 != NULL, L2 = <anything>>
  2. 不满足，递归，if(!L1)发送L1->next, L2
  3. 继续递归，直到L1为 NULL（这将是next列表中的最后一个，因此是结尾），然后将 L2 分配给该L1指针（这又是最后一个next）。
  4. 始终为结果返回 L1。递归的最终退出将返回列表的头部。
于 2013-01-29T04:41:24.493 回答