LeetCode 复杂链表的复制

题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

解题

题目的意思很简单，就是返回一个一模一样的链表头结点。由于随机指针的存在，链表的复制不能够像正常链表那样直接遍历，也因此没想明白要怎么做，最后翻了题解，才发现又是我最烦的递归。

这道题采用的递归解法其实本质就是遇到问题再解决问题，在还没有开始复制之前，所有的复制结点都是虚无的，要让这些结点和已知的结点一一对应起来就需要一个map数据结构。用来对应新旧两个链表的结点。这样从第一个结点入手，当这个结点不在map中时，就立刻创建这个结点并于原链表中的相应结点建立对应关系。之后的每一个结点都可以根据这样的逻辑进行创建，而因为有map这个数据结构的存在，这样每个结点都不是虚空存在的，而是可以在map中找到与之对应的结点。可以解决随机结点创建的问题。具体代码如下：

class Solution {
public:
    unordered_map<Node*, Node*> um;  // 用来存储两个链表，结点之间一一对应
    Node* copyRandomList(Node* head) {
        if (head == NULL) {  // 如果链表本就为空，那么直接返回空
            return NULL;
        }
        // 遵循边遍历边创建的原则
        if (!um.count(head)) {  // 如果此时哈希表中没有这个结点，就直接创建
            Node* headNew = new Node(head->val);  // 初始化一个相同的结点
            um.insert(make_pair(head, headNew));  // 将这两个位置一样的结点对应起来
            headNew->next = copyRandomList(head->next);  // 同理下一个结点也应该这样拷贝，依旧遵循上面的原则
            headNew->random = copyRandomList(head->random);
        }
        // 如果这个结点已经在哈希表中存在，那么就直接返回
        return um[head];
    }
};