如何在不使用递归的情况下将链接列表复制到另一个列表

Question

我在研究数据结构和链接列表，但我没有得到如何在不递归的情况下创建链接列表副本的概念。有人可以解释这一点。

Answer 1

没有递归===使用迭代。 P代码：

LinkedList *l1 = (the_head), *l2 = copy_node(l1); 
for (tmp l1->next; tmp != NULL; tmp = tmp->next, l2 = l2->next) { 
    l2->next = copy_node(tmp); 
} 

Answer 2

没有理由为此使用递归 - 简单的迭代很好地工作。复制节点。如果指向下一个节点的指针不为空，则为下一个节点重复该过程（并将刚复制的节点中的next链接指向您复制的下一个节点）。

Answer 3

问题的简单方法链表复制到一个空的列表，下面是一个使用递归，

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

Node* copy_list(Node* list) { 
    if (list == NULL) return NULL; 

    Node* result = new Node; 
    result->value = list->value; 
    result->next = copy_list(list->next); 
    return result; 
} 

，但如果你不想使用递归，那么你必须手动，复制每个不被清空列表使用循环，直到你得到（节点） - >下一个= NULL作为检查。

Answer 4

如何使用

1. 声明两个指针：一个dst指针，这将是最终的功能结果，并next指针到指针，它总是保持指针的地址将接收下一个节点分配。指针指针next最初保存地址dst。

2. 虽然我们仍然有节点复制，（src != NULL），请执行下列操作：

   • 分配一个新的节点，产生的指针分配给*next。
   • 将节点数据从src复制到*next。
   • 指定next以保存我们刚刚分配的node->next成员的地址。该会员可使用&(*next)->next获得。
   • 将输入源指针前移到其下一个节点：src = src->next。
   • 重复（2）。

3. 一旦完成，总是*next的值为NULL。这可以确保最终添加到列表中的节点（如果有）具有NULL，因为它的next指针。如果根本没有将节点添加到列表中（例如，当我们调用函数时，src是NULL），则代之以将dst的值设置为NULL，因为它是当前在next中保存的dst的地址。

4. 返回作为函数结果的dst的值。

该算法的代码如下所示：

typedef struct Node 
{ 
    int data; 
    struct Node *next; 
} Node; 

Node* CopyList(const Node* src) 
{ 
    Node *dst = NULL, **next = &dst; 
    while (src) 
    { 
     // allocate new node 
     *next = malloc(sizeof(**next)); 
     if (*next) 
     { 
      // copy_node() for complex duplication 
      (*next)->data = src->data; 

      // reposition our next-link to the address of ptr->next 
      // of the node we just added. 
      next = &(*next)->next; 

      // and finally, advance the source pointer 
      src = src->next; 
     } 
     else 
     { 
      perror("Failed to allocate node."); 
      exit(EXIT_FAILURE); 
     } 
    } 
    *next = NULL; 
    return dst; 
} 

注：这也是建立从串行输入文件前向链接列表的好方法。它确保头只被初始化一次，并且每个后续节点总是被添加到末节点的指针next。

Answer 5

一个简单的，重复的逻辑的伪代码将是：在原来的列表头，origHead

1. 开始。
2. 设置一个临时指针指向原始列表的头部，tempNode = origHead。
3. 如果tempNode = NULL，转到步骤17。
4. 如果tempNode != origHead，转到步骤10。
5. 分配内存对于复制列表的头部，copyListHead。
6. 设置copyListHead->next至NULL。
7. 设置一个临时指针指向复制列表的头部，copyListTempNode = copyListHead。
8. tempNode = tempNode->next。
9. 转到第3步。
10. 为节点分配内存newCopyNode。
11. 复制tempNode->data至newCopyNode->data。
12. 将newCopyNode->next设置为NULL。
13. 点copyListTempNode->next至newCopyNode。
14. copyListTempNode = newCopyNode。
15. tempNode = tempNode->next。
16. 转到步骤3.
17. 停止。