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

Question

我正在尝试使用 LinkedList 类的 duplicate() 方法制作链接列表的拷贝。我整天都在为如何使这种方法起作用而绞尽脑汁。

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

首先，您混淆了指针和数据的作用。

所有节点都有到下一个节点的“链接”。如果你想复制一个列表，你想创建每个节点的拷贝，并连接它们。这意味着您不应将新节点连接到旧节点，而应仅连接它们之间的新节点。

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;

}