链表问题

Question

可能的重复：
复制链接列表

你好 stackoverflow！我正在尝试了解有关链表的更多信息，因此我正在尝试创建一个深度复制链表的函数。我已经控制住了这一切。困难的部分是输入列表将包含引用列表中其他随机节点的节点。

第一个问题是我不知道如何在列表中创建“随机”节点。截至目前，我只有等于“下一个”节点的“随机”节点。

例如... pNext 引用下一个值，但 pReference 将引用列表中的随机节点。就像 pReference 1 引用 3、2 引用 4、3 引用 1 和 4 引用 1 一样。

第二个问题是我的代码正在处理“随机”节点值，但它依赖于原始副本。我希望它是一个深层副本，而不依赖于原始版本。

#include <iostream>
#include <stdio.h>

using namespace std;

struct Node
{
    int Number; // An integer value.
    Node *pNext; // A pointer to the next node within the list.
    Node *pReference; // A pointer to a random node within the list.
};

void push(Node** head, int data, Node* reference)
{
    Node* newNode = new Node; 
    newNode->Number = data;
    newNode->pNext = *head;
    newNode->pReference = reference;
    *head = newNode;
}

Node* DuplicateLinkedList(Node *head)
{
    Node* current = head;
    Node* newHead = NULL;
    Node* newTail = NULL;

    while(current != NULL)
    {
        if(newHead == NULL)
        {
            push(&newHead, current->Number, (current->pReference));
            newTail = newHead;
        }
        else
        {
            push(&(newTail->pNext),current->Number, (current->pReference));
            newTail = newTail->pNext;
        }
        current = current->pNext;
    }

    return newHead;
}

int main()
{
    Node* headOfList= NULL;

    //Creating List for verification.
    for(int i=6; i>=1;i--)
    {
        push(&headOfList, i, headOfList);
    }

    //Call duplicate function.
    Node* copiedList = DuplicateLinkedList(headOfList);

    //Output for verification
    cout << endl << "Original: " << endl;
    while(headOfList != NULL)
    {
        cout << "Number: " << headOfList->Number << " ";
        cout << "pNext: " << headOfList->pNext << " ";
        cout << "pReference: " << headOfList->pReference << " " << endl;
        headOfList = headOfList->pNext;
    }
    cout << endl << endl;

    cout << endl << "Copied: " << endl;
    while(copiedList != NULL)
    {
        cout << "Number: " << copiedList->Number << " ";
        cout << "pNext: "  << copiedList->pNext << " ";
        cout << "pReference: " << copiedList->pReference << " " << endl;
        copiedList = copiedList->pNext;
    }
    cout << endl << endl;


    system("pause");
}

Answer 1

使用 std::map 来存储原始指针和新指针之间的转换。

遍历列表两次：第一次创建新节点（将 pReference 设置为 NULL）并填充映射，第二次通过在映射中查找来填充 pReference 成员。

未经测试的代码：

Node* CopyNode(Node* src)
{
  if (src == NULL) return NULL;

  Node* newNode = new Node;
  newNode->number = src->number;
  newNode->pNext = NULL;
  newNode->pReference = NULL;

  return newNode;
}

Node* DeepCopy(Node* head)
{
  if (head == NULL) return NULL;

  std::map<Node*, Node*> mappings;

  Node* newHead = copyNode(head);
  mappings[head] = newHead;

  Node* newCurrent = newHead;
  for (Node* next = head->pNext; next != NULL; next = next->pNext)
  {
    Node* copy = CopyNode(next);
    mappings[next] = copy;

    newCurrent->pNext = copy;
    newCurrent = copy;
  }

  for (Node* current = head; current != NULL; current = current->pNext)
  {
    Node* newCurrent = mappings[current];
    newCurrent->pReference = mappings[current->pReference];
  }

  return newHead;
}

Answer 2

这是一个非常巧妙的算法，当你没有列表的大小时，我学会了在 O(N) 时间内从列表中获取随机元素。

Node* GetRandomNode(Node* head)
{
 int i = 1;
 srand ( time (NULL) );
 Node* temp = head;
 while ( head != NULL )
 { 
   if ( rand() % i == 0 ) temp = head;
   head = head->pNext;
   i++; 
 }

 return temp;
}

因此，您只需使用每个节点的列表头调用此函数即可获得均匀分布的随机节点。

至于深度复制问题，您只需分配一个新节点并将节点的值复制到其中即可。

Answer 3

简化一下怎么样。
我通常先编写递归解决方案，然后将其转换为循环：

Node* DuplicateLinkedList(Node* list)
{
    std::map<Node*,Node*>   nodeMap;
    Node* result = DuplicateNode(nodeMap, list);
    resetRandomNodes(nodeMap, result);
    return result;
}

Node* DuplicateNode(std::map<Node*,Node*>& nodeMap, Node *node)
{
    if (node== NULL)
    {    return NULL;
    }

    Node* result = new Node(node->Number, 
                            // Recursively copy the next element
                            DuplicateNode(nodeMap, node->pNext),
                            // For now store the original rand element
                            // We will fix this by iterating over the list again 
                            node->pReference
                           );
    // Keep a record of which node maps to which new node.
    nodeMap[node] = result;

    return result;
}

void resetRandomNodes(std::map<Node*,Node*>& nodeMap, Node *node)
{
    if (node== NULL)
    {    return;
    }

    // Remember we stored the original random node (from the src list) in pReference.
    // Now we must replace this with the correct value. We can look this up in the
    // nodeMap we created when we copied the loop.
    node->pReference = nodeMap[node->pReference];

    // Recursively go through list.
    resetRandomNodes(nodeMap, node->pNext);
}

现在为了提高效率，您只需将递归转换为循环即可。应该是比较琐碎的。完成此操作后，您可以将这三个功能合并为一个。