C++如何创建链接列表的副本作为类对象？

Question

我想使用LinkedList类的duplicate（）方法制作链接列表的副本。我一直在摸索着如何使这种方法奏效。

重复的方法需要做一个精确的副本，返回一个指向新列表的指针。我希望能够在新列表上调用LinkedList方法。我应该返回一个LinkedList指针吗？或节点指针？我觉得我在这里完全错过了一些简单的东西。

我该如何将新头节点的位置存储在LinkedList指针中？

//LinkedList.h 
#pragma once 

#include<string> 

using namespace std; 

struct Node { 
    string nodeData; 
    Node* nextNode; 
}; 

class LinkedList { 
public: 
    LinkedList(); 

    ~LinkedList(); 

    bool insert(string givenData); 

    bool remove(string givenData); 

    void print() const; 

    int count() const; 

    int find(string givenData) const; 

    bool removeAll(); 

    LinkedList* duplicate() const; 

private: 
    Node* head; 
}; 


//LinkedList.cpp duplicate() method 
LinkedList* LinkedList::duplicate() const { 
    LinkedList* newList; 
    Node* newHeadNode = new Node; 
    Node* newNode = new Node; 

    newHeadNode->nodeData = head->nodeData; 
    newHeadNode->nextNode = head->nextNode; 

    Node* currentNode = head->nextNode; 
    Node* previousNode = head; 

    while ((currentNode) && (newNode->nodeData > currentNode->nodeData)) { 
     previousNode = currentNode; 
     currentNode = currentNode->nextNode; 

     newNode->nextNode = previousNode->nextNode; 
     previousNode->nextNode = newNode; 
    } 
} 

Answer 1

你duplicate()代码中有几个逻辑问题。

该代码可以被简化为以下：

LinkedList::LinkedList() 
    : head(NULL) 
{ 
} 

LinkedList* LinkedList::duplicate() const 
{ 
    LinkedList* newList = new LinkedList; 

    Node* currentNode = head; 
    Node* previousNode = NULL; 

    while (currentNode) 
    { 
     Node* newNode = new Node; 
     newNode->nodeData = currentNode->nodeData; 
     newNode->nextNode = NULL; 

     if (!newList->head) 
      newList->head = newNode; 

     if (previousNode) 
      previousNode->nextNode = newNode; 
     previousNode = newNode; 

     currentNode = currentNode->nextNode; 
    } 

    return newList; 
} 

这就是说，如果一个Node *tail成员添加到LinkedList，然后duplicate()可以在insert()，其本身可以大大简化方面来实现：

LinkedList::LinkedList() 
    : head(NULL), tail(NULL) 
{ 
} 

bool LinkedList::insert(string givenData) 
{ 
    Node* newNode = new Node; 
    newNode->nodeData = givenData; 
    newNode->nextNode = NULL; 

    if (!head) 
     head = newNode; 

    if (tail) 
     tail->nextNode = newNode; 
    tail = newNode; 

    return true; 
} 

LinkedList* LinkedList::duplicate() const 
{ 
    LinkedList* newList = new LinkedList; 

    Node* currentNode = head; 
    while (currentNode) 
    { 
     newList->insert(currentNode->nodeData); 
     currentNode = currentNode->nextNode; 
    } 

    return newList; 
} 

如果添加tail是不是一种选择，那么至少考虑添加一个可选的Node*参数insert()代替：

Node* LinkedList::insert(string givenData, Node *after) 
{ 
    Node* newNode = new Node; 
    newNode->nodeData = givenData; 
    newNode->nextNode = NULL; 

    if (!head) { 
     head = newNode; 
    } 
    else { 
     if (!after) { 
      after = head; 
      while (after->nextNode) { 
       after = after->nextNode; 
      } 
     } 
     newNode->nextNode = after->nextNode; 
     after->nextNode = newNode; 
    } 

    return newNode; 
} 

LinkedList* LinkedList::duplicate() const 
{ 
    LinkedList* newList = new LinkedList; 

    Node* currentNode = head; 
    Node *newNode = NULL; 

    while (currentNode) 
    { 
     newNode = newList->insert(currentNode->nodeData, newNode); 
     currentNode = currentNode->nextNode; 
    } 

    return newList; 
} 

Answer 2

如果你试图做一个deep copy（赋值运算符）链表，可以考虑使用recursion。

比较this针对通过的第二个列表的参考。如果它们不一样，则列表clear。如果传入的列表中有头指针，则调用递归方法。该方法需要node* n。检查它是否退出，如果有，请用n的下一个指针调用它自己。然后它应该将n的数据添加到列表的头部。因为这是递归的，所以AddHead调用会在堆栈上等待，直到递归完成，然后以相反顺序调用，从而导致列表的正确排序。

如果你只是在做一个拷贝构造函数，你可以简单地设置*this等于传入的列表。例如。

LinkedList (const LinkedList& other) { 
    count = 0; 
    head = nullptr; 
    *this = other; 
} 

Answer 3

您正在混淆指针和数据的作用，开始。

所有节点都有到下一个节点的“链接”。如果要复制列表，则需要创建每个节点的副本，并将它们连接起来。这意味着你不应该将新节点连接到旧节点，而只是将它们之间的新节点连接起来。

newHeadNode->nextNode = head->nextNode;因此是错误的。

此外，你的类有一个插入方法，你可以使用，并且可能已经正确地创建了一个节点并设置了旧的尾节点指针。

你的函数体应该像

LinkedList* LinkedList::duplicate() const { 
    // create a new list 
    LinkedList* newList = new LinkedList(); 
    // start from the first node of the old list 
    currnode = this->head; 

    // until currnode is valid 
    while(currnode){ 
     // insert the data in the new list (the new list will deal with the pointers) 
     newList->insert(currnode->data); 
     // go to the next node of the old list 
     currnode = currnode->nextNode; 
    } 

    return newList; 

} 

Answer 4

看起来像雷米Lebeau在这里之前，我可以回到这里。唯一可以补充的是稍微更紧凑一点，更困惑的方式来编写duplicate。这是一个很好的例子，说明一个额外的间接程度如何能够节省一些工作，所以我会放在这里。

//LinkedList.cpp duplicate() method 
LinkedList* LinkedList::duplicate() const { 
    // make a new empty list 
    LinkedList* newList = new LinkedList; 

    //get the first node from the list to be duplicated 
    Node * getp = head; 

    //Here be where we get a bit weird. Rather than getting a pointer to the 
    //head node like we did with the source list, we are going to get a pointer 
    //to the head itself! Crazy, right? 
    //But if you think about it, it means we can use head just like any other 
    //pointer to a node (which it is) without having to write any special code 
    //specifically to handle the head or having to carry around previousNode 
    //pointers and other overhead 
    Node ** putpp = &newList->head; 

    //Loop through the source list 
    while (getp != NULL) 
    { 
     *putpp = new Node; //make a new node and insert it into the list 
          //wherever putpp is currently pointing, head or 
          //any node's next 
     (*putpp)->nodeData = getp->nodeData; // copy the source node's data 
     putpp = &(*putpp)->nextNode; // point at the new node's next so we can 
             // add the next new node 
     getp = getp->nextNode; // point at the next source node 
    } 
    *putpp = NULL; // null the last next pointer to end the list 
    return newList; 
}