【MEDIUM】Copy List with Random Pointer

发布于: 2018-12-08 18:13
阅读: 35
评论: 0
喜欢: 0

问题

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

分析过程

  • 输入:一个带有随机指针的链表
  • 输出:该链表的深拷贝
  • 思路:首先遍历链表,拷贝一份。拷贝的同时记录两个字典,1、旧链表的<节点, 索引>,2、新链表的<索引, 节点>。复制完一遍以后再次遍历,找旧链表中有随机指针的节点。依靠前面第 1 个字典,找出这个节点的索引,然后用这个索引在第 2 个字典里找到在新链表中的节点,赋值即可。

解决方法

#include <iostream>
#include <map>

class Node {
public:
    int val;
    Node *pointer;
    Node *next;
    
    Node(int val) {
        this->val = val;
        this->pointer = nullptr;
        this->next = nullptr;
    }
    
    Node *copy() {
        return new Node(val);
    }
};

Node *deepcopy(Node *root) {
    std::map<Node *, int> oldDict;
    std::map<int, Node *> newDict;
    
    Node *oldTmp = root;
    
    Node *newRoot = root->copy();
    Node *newTmp = newRoot;
    
    int index = 0;
    // 第一次遍历,拷贝链表,并且记录字典
    while (oldTmp) {
        // 新链表中的索引到节点
        newDict[index] = newTmp;
        // 旧链表中的节点到索引
        oldDict[oldTmp] = index;
        
        oldTmp = oldTmp->next;
        
        if (oldTmp) {
            newTmp->next = oldTmp->copy();
            newTmp = newTmp->next;
            index++;
        }
    }
    
    // 再次遍历
    oldTmp = root;
    index = 0;
    while (oldTmp) {
        Node *ptrNode = oldTmp->pointer;
        // 找到有随机指针的节点,联合两个字典找到目标节点
        if (ptrNode) {
            int ptrIndex = oldDict[ptrNode];
            newDict[index]->pointer = newDict[ptrIndex];
        }
        
        oldTmp = oldTmp->next;
        index++;
    }
    
    return newRoot;
}

int main(int argc, const char * argv[]) {
    // 0 -
    // 1  |
    // 2 -
    // 3 -
    // 4  |
    // 5 -
    Node root = Node(0);
    Node n1 = Node(1);
    Node n2 = Node(2);
    Node n3 = Node(3);
    Node n4 = Node(4);
    Node n5 = Node(5);
    
    root.next = &n1;
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    
    root.pointer = &n2;
    n3.pointer = &n5;
    
    Node *newRoot = deepcopy(&root);
    
    return 0;
}

Thanks for reading.

All the best wishes for you! 💕