【MEDIUM】Copy List with Random Pointer

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

问题

原题链接:https://leetcode.com/problems/copy-list-with-random-pointer/

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.

Note:

  • You must return the copy of the given head as a reference to the cloned list.

分析过程

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

解决方法

class Solution {
public:
    Node *copyNode(Node *node) {
        return new Node(node->val, nullptr, nullptr);
    }

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

Thanks for reading.

All the best wishes for you! 💕