【链表问题】打卡8：复制含有随机指针节点的链表

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢。

注：如果代码排版出现了问题麻烦通知我下，谢谢。

【题目描述】

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【难度】

尉：★★☆☆

【解答】

方法一：使用额外的存储空间

这道题的难点在于我们需要定位好随机指针，一个比较简单的解法就是把原节点与复制的节点关联起来，可以使用哈希表把他们关联起来。

首先把副节点全部创建出来，然后把原节点与对应的副节点用哈希表关联起来。关联的时候原节点作为key，副节点作为value。例如对于链表 1->2->3->null。创建副节点 1', 2', 3'。然后用哈希表关联起来：

key	value
1	1'
2	2'
3	3'

之后在把所有副节点连接成一个链表。在连接的时候，我们 可以通过哈希表很容易这找到对应的随机节点。

代码如下

 1//方法1：采用哈希表
 2public static Node1 copyListWithRand(Node1 head) {
 3    Map<Node1, Node1> map = new HashMap<>();
 4    Node1 cur = head;
 5    while (cur != null) {
 6        map.put(cur, new Node1(cur.value));
 7        cur = cur.next;
 8    }
 9    //把副节点连接起来
10    cur = head;
11    while (cur != null) {
12        map.get(cur).next = map.get(cur.next);
13        map.get(cur).rand = map.get(cur.rand);
14        cur = cur.next;
15    }
16    return map.get(head);
17}

这种方法的时间复杂度为 O(n), 空间复杂度也为 O(n)。

方法2

其实我们也可以不需要哈希表来辅助，也就是说 ，我们是可以做到空间复杂度为 O(1)的，我们可以把复制的副节点插入到原链表中去，这样也能把原节点与副节点进行关联，进而
定位到随机节点。例如，对于链表 1->2->3->null。首先生成副节点 1', 2', 3。然后把副节点插入到原节点的相邻位置，即把原链表变成 1->1'->2->2'->3->3'->null。

这样我们也可以在连接副节点的时候，找到相应的随机节点。例如 1 的随机节点是 3，则 1' 的随机节点是 3'。显然，1节点的随机节点的下一个节点就是 1'的随机节点。具体代码如下：

 1//方法二
 2public static Node1 copyListWithRand2(Node1 head){
 3    Node1 cur = head;
 4    Node1 next = null;
 5
 6    //把复制的节点插进去
 7    while (cur != null) {
 8        next = cur.next;
 9        Node1 temp = new Node1(cur.value);//复制节点
10        temp.next = cur.next;
11        cur.next = temp;
12        cur = next;
13    }
14    //在一边把复制的节点取出来一边连接。
15    cur = head;
16    next = null;
17    while (cur != null) {
18        next = cur.next.next;//保存原链表的下一个节点
19        cur.next.next = next != null ? next.next : null;
20        cur.next.rand = cur.rand != null ? cur.rand.next : null;
21        cur = next;
22    }
23    return head.next;
24}

采用这种方法的时候，由于随机节点有可能是空指针，随意写代码的时候要注意。

问题拓展

思考：如果是有两个随机指针呢？又该如何处理呢？三个呢？

【题目描述】

无

【要求】

无

【难度】

未知。

【解答】

提醒：别想太多了，保持清醒。

往期