用C语言编写一个程序，可以复制一个链表的副本。

Question

我正在编写一个C语言代码，将链表的内容复制到另一个链表中。我想知道是否有更有效的方法。

哪个更好？

struct node *copy(struct node *start1)
{
struct node *start2=NULL,*previous=NULL;

while(start1!=NULL)
{
    struct node * temp = (struct node *) malloc (sizeof(struct node));
    temp->info=start1->info;
    temp->link=NULL;

    if(start2==NULL)
    {
        start2=temp;
        previous=temp;
    }
    else
    {
        previous->link=temp;
        previous=temp;          
    }
    start1=start1->link;
}
return start2;
}

或者

struct node *copy(struct node *start1)
{
    if(start1==NULL) return;
    struct node *temp=(struct node *) malloc(sizeof(struct node));
    temp->info=start1->info;
    temp->link=copy(start1->link);
    return temp;
}

- user

---

你是在寻找运行时效率，还是更紧凑/优雅的实现方式？ - RonaldBarzell

我想有更优雅的方法来实现它。 - user

递归地完成这个任务会非常优雅，但你必须小心，以免出现堆栈溢出的情况。哈哈哈，今天的双关语自己就写出来了。但说真的，除非你使用尾递归语言，否则你只能递归到一定程度，而C语言不是尾递归语言。 - RonaldBarzell

@user1161318 真正的男人使用 goto 来进行递归 ;-) 虽然某些 C 编译器实现（例如：带扩展的 GCC？）可以优化尾递归 在某些情况下.. 但它必须是可进行尾递归优化的。 - user166390

@MohamedKALLEL，除非它被TCO'd，否则最好进行分析而不是猜测。即使那样，也是这样。 - Useless

Answer 1

对于将一个链表复制到另一个链表，你别无选择，只能遍历一个链表并将值复制到第二个链表中，在总共O(n)的时间内完成。你已经在做了。除非存储的元素之间存在某种关系，否则没有更好的方法。

递归解决方案可能更好看，但实际上效率会更低。

编辑：对于修改后的问题

迭代版本更好。

注意：LOC与效率没有直接关系。

- axiom

---

能否至少减少代码行数？ - user

代码行数与效率无关。你的问题是如何提高效率，我想我已经回答了 :) - axiom

您可以减少代码行数。请参考我的答案。 - MOHAMED

但这并不一定会使其更有效率。另外请查看我的评论。 - axiom

Answer 2

不使用递归，这是最简洁的方式：

struct node *copy(struct node *org)
{
struct node *new=NULL,**tail = &new;

for( ;org; org = org->link) {
    *tail = malloc (sizeof **tail );
    (*tail)->info = org->info;
    (*tail)->link = NULL;
    tail = &(*tail)->link;
    }
return new;
}

- wildplasser

Answer 3

为了速度，实际上可能有更好的方法。像往常一样，唯一真正的方法是进行基准测试。

根据相对的迭代成本（这可能取决于您分配节点的方式和顺序，以及缓存和内存架构），与自由存储器分配相比（这可能取决于堆的状态，有多少其他线程可能正在访问它，主机操作系统中的物理内存状态等），进行单个块中所需节点的空间分配可能更快。因此，可以花费一个迭代计算源列表的长度，然后在单个块中为所有所需节点分配空间，最后再花费第二个迭代来链接节点数组。

就像我说的那样，我并不保证它会更快（而且它肯定更丑），但在某些系统、某些编译器和某些条件下，它可能会更快。当然，如果你的代码的其余部分假定你可以随意释放单个节点，那么这是行不通的。

---

在优雅方面，递归自然胜出。

通常来说，简单的迭代方法是一个很好的折中方案，既能保持优雅但不会像使用高级TCO编译器那样可能导致程序崩溃，也不会像上述方法那样有些丑陋，需要加上解释性注释。

- Useless

---

我正在为这个问题编写一个程序，因为它是我的数据结构教材中的练习题。不过还是感谢你对效率方面的见解！ :) - user