138. 复制带随机指针的链表

发表于 更新于 分类于 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random→Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random→y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

138_example1 
1
2
>输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
>输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
1
2
3
4
5
6
7
8
9
10
11
12
>// Definition for a Node.
>class Node {
   int val;
   Node next;
   Node random;

   public Node(int val) {
          this.val = val;
          this.next = null;
          this.random = null;
   }
>}

题解

看到这道题第一个反应就是这个链表不是一个普通的链表，本质上它可以转化为有向图，所以这道题本质可以说是图的深拷贝。下面这张图就是我们将这个链表转化为一张图之后的样子。

138_diagram

所以，由此我们可以采取类似BFS的思路对这个链表进行深拷贝。当遍历到一个节点的时候，我们可以对当前节点的下一个节点和随机节点分别进行拷贝。为了保证一个不会重复拷贝已经拷贝过的节点，我们可以使用哈希表对节点的拷贝情况进行记录。以下是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {

    Map<Node,Node> map = new HashMap<Node,Node>();

    public Node copyRandomList(Node head) {
        if (head == null) return null;
        
        if (!map.containsKey(head)) {
            Node newHead = new Node(head.val);
            map.put(head, newHead);
            newHead.next = copyRandomList(head.next);
            newHead.random = copyRandomList(head.random);
        }
        return map.get(head);
    }
}

另外一种思路是在评论区里看到的，感觉也非常的容易理解，也记录一下。思路非常清晰，首先遍历一遍链表，拷贝每个节点的值到新节点中，并且放入哈希表中记录，但是并拷贝节点的两个指针。然后第二次遍历，这个时候，我们新创建的每个指针的节点都储存在哈希表中了，我们就直接可以用next和random指针直接指向了。总体的思路就是，先创建单个节点，再将他们连接起来。下面是代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Map<Node,Node> map = new HashMap<Node,Node>();
        for (Node node = head; node != null; node = node.next) {
            map.put(node, new Node(node.val));
        }
        for (Node node = head; node != null; node = node.next) {
            Node newNode = map.get(node);
            newNode.next = map.get(node.next);
            newNode.random = map.get(node.random);
            map.put(node, newNode);
        }
        return map.get(head);
    }
}

附

注意到第一种解法的代码中，我们首先将newNode加入到哈希表中，之后再改变它的两个指针，由此可以判断出我们加入哈希表中的Object实际上应该是一个引用，所以我们改变原本的值就会直接影响到哈希表中存储的值，写了以下代码进行验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Main {
    public static void main(String[] args) {
        class Node {
            Node next;
            int val;
            public Node(int value) {
                this.val = value;
            }
        }
        Map<Node, Node> map = new HashMap<>();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        node1.next = node2;
        node2.next = null;
        Node newNode = new Node(node1.val);
        map.put(node1, newNode);
        newNode.val = 4;
        newNode.next = node2;
        System.out.println(map.get(node1).val);
        System.out.println(map.get(node1).next.val);
    }
}

/**
* 输出：
* 4
* 2
/