[数据结构与算法]LeetCode 138. 复制带随机指针的链表

若是普通单链表，则依次遍历每个节点，每次新建一个节点并拷贝原节点中的值val即可。每个节点都带有一个随机指针，造成的难点在于：如果这个random随机指针指向的节点，先前已经拷贝过了，则需要复用先前拷贝的那个节点。

解法一：借助哈希表

所以比较直观的想法就是，用一个Map来记录新旧节点的映射关系（key为旧的节点，value为新的节点），当准备对一个旧的节点进行拷贝时，先查一下Map，如果先前已经拷贝过，则直接从Map中取出对应的新节点；若没有拷贝过，则新建一个节点，并插入到Map

通过引入一个哈希表，来完成整个拷贝过程，这种做法的额外空间复杂度是$O(n)$，时间复杂度是$O(n)$

两次遍历

一个最简单的做法是，两次遍历。第一次遍历原链表，对每个旧的节点，依次新建一个节点，并插入到Map；第一次遍历结束后，我们已经得到了全部的新节点。接下来只要把这些新的节点按照顺序连接起来即可；则，第二次遍历原链表，每次从Map中取出需要的节点即可。

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        // 第一次遍历, 先把所有新节点构造出来
        for (Node cur = head; cur != null; cur = cur.next) {
            map.put(cur, new Node(cur.val));
        }
        // 第二次遍历, 将所有的新节点连接起来
        for (Node cur = head; cur != null; cur = cur.next) {
            Node newNode = map.get(cur);
            newNode.next = map.get(cur.next);
            newNode.random = map.get(cur.random);
        }
        return map.get(head);
    }
}

递归

除此以外，可以用递归的思路来做。设一个函数copy(Node x)，其含义是深拷贝以节点x开头的整个链表，并返回新的链表头。仍然需要借助一个Map来存放已经构造出来的节点

class Solution {
    public Node copyRandomList(Node head) {
        return copy(head, new HashMap<>());
    }
    
    private Node copy(Node x, Map<Node, Node> map) {
        if (x == null) return null;
        // 已经构造过, 直接返回
        if (map.containsKey(x)) return map.get(x);
        // 否则, 构造一个新的节点
        Node newNode = new Node(x.val);
        // 将新构造的节点放入 map
        map.put(x, newNode);
        // 递归构造 next 和 random
        newNode.next = copy(x.next, map);
        newNode.random = copy(x.random, map);
        return newNode;
    }
}

解法二：节点拆分

上面的做法都需要借助哈希表，额外空间复杂度是$O(n)$，能不能有额外空间复杂度为$O(1)$的做法呢？答案是有的。
仔细思考一下，我们为什么需要一个哈希表？
我们仅仅是需要借助哈希表，来找到某一个旧的节点，对应的新节点。
那么，如果我们将每一个新节点，插入到其对应的旧节点的后面，这样一来，不需要借助哈希表，也能够根据旧节点，定位到其对应的新节点。

第一次遍历，将所有新节点构造出来，并插入到原链表当中。
第二次遍历，对每个新节点，填补其random指针
第三次遍历，将新旧链表进行拆分

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        // 构造全部新节点
        for (Node cur = head; cur != null; cur = cur.next.next) {
            Node newNode = new Node(cur.val); // 构造一个新节点
            newNode.next = cur.next; // 将新节点插入到当前节点后面
            cur.next = newNode;
        }
        // 填补新节点的 random 域
        for (Node cur = head; cur != null; cur = cur.next.next) {
            Node newNode = cur.next;
            if (cur.random != null) newNode.random = cur.random.next;
        }
        // 拆分两个链表
        Node res = head.next;
        for (Node cur = head; cur != null; cur = cur.next) {
            Node newNode = cur.next;
            cur.next = cur.next.next;
            if (newNode.next != null) newNode.next = newNode.next.next;
        }
        return res;
    }
}

关于力扣官方题解中提到的：“读者可自行尝试将3次遍历缩短为2次遍历”

也就是尝试将填补random域和拆分链表进行合并。

经过尝试后发现行不通。原因如下：

因为遍历是从左往右的，那么在遍历到中间某个位置i时，i之前的部分，新旧链表已经被拆分开，而对于i之后的新节点，需要填补其random域，而其random域完全有可能指向i之前的节点。而i之前的部分已经做了拆分，对于i之前的节点，无法再根据旧节点找到对应的新节点。也就是说，i之前的部分，新旧节点之间的联系已经断掉了。所以无法填补新节点的random域。

但是，如果题目允许修改原链表的结构的话，则可以通过2次遍历得到新链表。

在遍历时，仅对新节点进行拆分，即，只改变新节点的next指针，而不把旧节点指向新节点的next指针断开。这样能够保证无论何时都能根据旧节点找到对应的新节点。即能顺利完成对新节点的random域的填充。
只是，这样最后的链表结构将变成下面这样子：

这样，只能把新链表拆分出来，而原链表的结构则被改变了。

代码如下

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        // 构造全部新节点
        for (Node cur = head; cur != null; cur = cur.next.next) {
            Node newNode = new Node(cur.val); // 构造一个新节点
            newNode.next = cur.next; // 将新节点插入到当前节点后面
            cur.next = newNode;
        }
        // 填补新节点的 random 域 + 拆分
        for (Node cur = head; cur != null; ) {
            Node nextCur = cur.next.next;
            Node newNode = cur.next;
            if (cur.random != null) newNode.random = cur.random.next;
            if (newNode.next != null) newNode.next = newNode.next.next;
            cur = nextCur;
        }
        // 拆分两个链表
        return head.next;
    }
}

尝试提交了一下这种做法的代码，发现修改原链表的结构是不允许的

阅读世界，共赴山海

423全民读书节，邀你共读