如何在C中复制链表？

Question

这是我复制列表的功能。错误在于它总是将第一个元素复制两次。我究竟做错了什么？

Node *copy(Node *list) {

  Node *newlist, *p;

  p = malloc(sizeof(Node));
  newlist = p;

  while (list != NULL) {
      strcpy(p->airport, list->airport);
      p = p->next;
      p = malloc(sizeof(Node));
      list = list->next;
  }

  return newlist;
}

Answer 1

将其分成 3 部分。

// Part 1 - the null list
if (list == NULL) return NULL;

// Part 2 - the head element
Node *newHead = malloc(sizeof(Node));
strcpy(newHead->airport, list->airport);

// Part 3 - the rest of the list
Node *p = newHead;
list = list->next;
while(list != NULL) {
    p->next = malloc(sizeof(Node);
    p=p->next;
    strcpy(p->airport, list->airport);
    list = list->next;
}
p->next = NULL;  // terminate last element.

Answer 2

怎么样：

Node *copy(Node *list) {

  Node *newlist, *p, *prev;

  newlist = p = NULL;

  while (list != NULL) {
      p = malloc(sizeof(*p));
      strcpy(p->airport, list->airport);
      if (!newlist)
          newlist = p;
      else
          prev->next = p;
      prev = p;
      list = list->next;
  }
  prev->next = NULL;
  return newlist;
}

您需要保留对前一个节点的引用，以便在下一次迭代中更新其

next

。

Answer 3

只需更改这些行的顺序即可

  p = p->next;
  p = malloc(sizeof(Node));

到

  p->next = malloc(sizeof(Node));
  p = p->next;

Answer 4

这些线不可能是正确的：

p = p->next;
p = malloc(sizeof(Node));

设置新值

p

，然后覆盖它。

我建议您将新节点的

malloc

放入

while

循环内。您还需要在分配后将

p->next

设置为某个值，并保留指向分配的第一个新节点的指针。

Answer 5

struct node* copyList(struct node* source) {
    struct node* dest = NULL;

    while (source != NULL) {
        dest = insertBack(dest, source->data);
        source = source->next;
    }
    return dest;
}

Answer 6

您可以使用间接指针，以便在循环期间修改每个“下一个”指针，即使列表为空也是如此。在其他语言中，您可以通过创建一个虚拟节点来实现此目的，该虚拟节点的“下一个”指针等于列表的“头”指针，但在 C 中，所需的只是一个指向指针的指针。

Node *copy(Node *list_node) {
    Node *new_list, **indirect;

    /* 
     * Every loop, "indirect" points to the following "next" pointer
     * that will be modified when we allocate a new Node. 
     */
    indirect = &new_list
    while (list_node != NULL) {
        Node *np;

        np = malloc(sizeof(Node));
        strcpy(np->airport, list_node->airport);
        *indirect = np;
        indirect = &np->next;
        list_node = list_node->next;
    }
    /* 
     * At the end of the loop, terminate the linked list with
     * a NULL "next" pointer, which the variable "indirect" is pointing to
     * right after the loop ends.
     */
    *indirect = NULL;

    /*
     * The variable "new_list" is not uninitialized. 
     * Either it was modified through the pointer "indirect" during the loop.
     * or else the loop never ran, so it's null due to the above line of code.
     * Either it points to the start of the list or it's null, so return it.
     */
    return new_list;
}