链表问题

Question

可能重复：
Copy a linked list

计算器您好！我想了解更多关于链接列表，所以我想创建一个深层复制链接列表的函数。我已经掌握了这个。难点在于输入列表将包含引用列表中其他随机节点的节点。

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

例如... 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); 
} 

现在，使其有效的，你只需要递归转化为一个循环。应该是相对微不足道的。一旦你完成了，你可以将三个函数合并成一个。