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

问题:

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.

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:

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.

回答1:

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?

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.

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);

回答2:

This is an excellent question 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):

# 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 not what you're doing. The variable you're returning points to heap-allocated memory, which will survive function exit.

回答3:

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:

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.

回答4:

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

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;
}

回答5:

Since you need a copy of 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 delete the nodes of linked list.

回答6:

@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.

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.

回答7:

As others have pointed out, you need to call new for each node 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.

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 delete to free it when you are done with the new list, from outside the function).