编写一个函数来复制 C++ 中的链表

Coding a function to copy a linked-list in C++

提问by Pat Murray

I need to implement an auxilliary function, named copyList, having one parameter, a pointer to a ListNode. This function needs to return a pointer to the first node of a copy of original linked list. So, in other words, I need to code a function in C++ that takes a header node of a linked list and copies that entire linked list, returning a pointer to the new header node. I need help implementing this function and this is what I have right now.

我需要实现一个名为 copyList 的辅助函数，它有一个参数，一个指向 ListNode 的指针。该函数需要返回一个指向原始链表副本第一个节点的指针。因此，换句话说，我需要用 C++ 编写一个函数，它接受一个链表的头节点并复制整个链表，返回一个指向新头节点的指针。我需要帮助来实现这个功能，这就是我现在所拥有的。

Listnode *SortedList::copyList(Listnode *L) {

    Listnode *current = L;  //holds the current node

    Listnode *copy = new Listnode;
    copy->next = NULL;

    //traverses the list
    while (current != NULL) {
       *(copy->student) = *(current->student);
       *(copy->next) = *(current->next);

        copy = copy->next;
        current = current->next;
    }
    return copy;
}

Also, this is the Listnode structure I am working with:

此外，这是我正在使用的 Listnode 结构：

struct Listnode {    
  Student *student;
  Listnode *next;
};

Note: another factor I am running into with this function is the idea of returning a pointer to a local variable.

注意：我在使用此函数时遇到的另一个因素是返回指向局部变量的指针的想法。

采纳答案by André Caron

The first question you need to ask yourself is what the copy semantics are. In particular, you're using a Student*as node contents. What does copying node contents mean? Should we copy the pointer so that the two lists will point to (share) the same student instances, or should you perform a deep copy?

您需要问自己的第一个问题是复制语义是什么。特别是，您正在使用 aStudent*作为节点内容。复制节点内容是什么意思？我们应该复制指针以便两个列表指向（共享）相同的学生实例，还是应该执行深层复制？

struct Listnode {    
  Student *student; // a pointer?  shouldn't this be a `Student` object?
  Listnode *next;
};

The next question you should ask yourself is how you will allocate the nodes for the second list. Currently, you only allocate 1 node in the copy.

您应该问自己的下一个问题是如何为第二个列表分配节点。目前，您只在副本中分配 1 个节点。

I think you code should look more like:

我认为你的代码应该看起来更像：

Listnode *SortedList::copyList(Listnode *L) {

    Listnode *current = L;

    // Assume the list contains at least 1 student.
    Listnode *copy = new Listnode;
    copy->student = new Student(*current->student);
    copy->next = NULL;

    // Keep track of first element of the copy.
    Listnode *const head = copy;

    // 1st element already copied.
    current = current->next;

    while (current != NULL) {
       // Allocate the next node and advance `copy` to the element being copied.
       copy = copy->next = new Listnode;

       // Copy the node contents; don't share references to students.
       copy->student = new Student(*current->student);

       // No next element (yet).
       copy->next = NULL;

       // Advance 'current' to the next element
       current = current->next;
    }

    // Return pointer to first (not last) element.
    return head;
}

---

---

If you prefer sharing student instances between the two lists, you can use

如果您更喜欢在两个列表之间共享学生实例，您可以使用

copy->student = current->student;

instead of

代替

copy->student = new Student(*current->student);

回答by paxdiablo

This is an excellentquestion since you've done the bulk of the work yourself, far better than most "please do my homework for me" questions.

这是一个很好的问题，因为你自己完成了大部分工作，比大多数“请为我做作业”的问题要好得多。

A couple of points.

几点。

First, what happens if you pass in an empty list? You probably want to catch that up front and just return an empty list to the caller.

首先，如果你传入一个空列表会发生什么？您可能想提前抓住它，然后将一个空列表返回给调用者。

Second, you only allocate the first node in the copy list, you need to do one per node in the original list.

其次，您只分配复制列表中的第一个节点，您需要为原始列表中的每个节点分配一个。

Something like (pseudo-code (but C++-like) for homework, sorry):

类似于（用于作业的伪代码（但类似于 C++），抱歉）：

# Detect empty list early.

if current == NULL:
    return NULL;

# Do first node as special case, maintain pointer to last element
# for appending, and start with second original node.

copy = new node()
last = copy

copy->payload = current->payload
current = current->next

# While more nodes to copy.

while current != NULL:
    # Create a new node, tracking last.

    last->next = new node()
    last = last->next

    # Transfer payload and advance pointer in original list.

    last->payload = current->payload
    current = current->next

# Need to terminate new list and return address of its first node

last->next = NULL
return copy

And, while you're correct that you shouldn't return a pointer to a local stack variable, that's notwhat you're doing. The variable you're returning points to heap-allocatedmemory, which will survive function exit.

而且，虽然您不应该返回指向本地堆栈变量的指针是正确的，但这不是您正在做的。您返回的变量指向堆分配的内存，它将在函数退出后继续存在。

回答by CtheGood

I have been trying to do the same thing. My requirements were:

1. Each node is a very basic and simple class (I moved away from the struct model).
2. I want to create a deep copy, and not just a pointer to the old linked list.

The way that I chose to do this is with the following C++ code:

我一直在尝试做同样的事情。我的要求是：

1. 每个节点都是一个非常基本和简单的类（我离开了结构模型）。
2.我想创建一个深拷贝，而不仅仅是一个指向旧链表的指针。

我选择这样做的方式是使用以下 C++ 代码：

template <class T>
Node <T> * copy(Node <T> * rhs)
{
    Node <T> * current = new Node<T>();
    Node <T> * pHead = current;
    for (Node <T> * p = rhs; p; p = p->pNext)
    {
        Node <T> * prev = current;
        prev->data = p->data;
        if (p->pNext != NULL)
        {
            Node <T> * next = new Node<T>();
            prev->pNext = next;
            current = next;
        }
        else
        {
            prev->pNext = NULL;
        }
    }
    return pHead;
}

This works well, with no errors. Because the "head" is a special case, there is a need for my implementation of a "current" pointer.

这很好用，没有错误。因为“头”是一个特例，所以需要我实现一个“当前”指针。

回答by Synetech

As others have pointed out, you need to call newfor eachnode in the original list to allocate space for a copy, then copy the old node to the new one and update the pointer in the copied node.

正如其他人所指出的那样，你需要调用new的每个原始列表节点为副本分配空间，然后复制旧节点到新的和更新的拷贝节点的指针。

another factor I am running into with this function is the idea of returning a pointer to a local variable.

我在这个函数中遇到的另一个因素是返回一个指向局部变量的指针的想法。

You are not returning a pointer to a local variable; when you called new, you allocated memory on the heap and are returning a pointer to that (which of course means that you need to remember to call deleteto free it when you are done with the new list, from outsidethe function).

您没有返回指向局部变量的指针；当您调用 时new，您在堆上分配了内存并返回一个指向该内存的指针（这当然意味着您需要记住delete在完成新列表后从函数外部调用以释放它）。

回答by howtechstuffworks

@pat, I guess you will get a seg_fault, because you create memory only once. You need to create memory(basically call 'new') for each and every node. Find out, where you need to use the 'new' keyword, to create memory for all the nodes.

@pat，我猜你会得到一个 seg_fault，因为你只创建了一次内存。您需要为每个节点创建内存（基本上称为“新”）。找出您需要在何处使用“new”关键字来为所有节点创建内存。

Once you are done with this, you need to link it to the previous node, since its a singly linked list, you need to maintain a pointer to the previous node. If you want to learn and should be able to remember all life, don't see any of the code mentioned above. Try to think the above mentioned factors and try to come up with your own code.

完成此操作后，您需要将其链接到前一个节点，因为它是一个单向链表，您需要维护一个指向前一个节点的指针。如果你想学习并且应该能够记住所有生活，不要看上面提到的任何代码。尝试考虑上述因素并尝试提出自己的代码。

回答by noMAD

The statement copy->next = current->nextis wrong. You should do

说法 copy->next = current->next是错误的。你应该做

Create the first node copy here
copy->student = current->student;
copy->next = NULL;
while(current->next!=NULL)
{
    Create new node TEMP here
    copy->next = TEMP;
    TEMP->student = current->student;
    TEMP->next = NULL;
    copy = TEMP;
}

回答by Mahesh

Since you need a copyof the linked list, you need to create a new node in the loop while traversing through the original list.

由于需要链表的副本，因此需要在遍历原始链表的同时在循环中创建新节点。

Listnode *startCopyNode = copy;

while (current != NULL) {
   *(copy->student) = *(current->student);
    copy->next = new Listnode;
    copy = copy->next;
    current = current->next;
}

copy->next = NULL;
return startCopyNode;

Remember to deletethe nodes of linked list.

记住delete链表的节点。