题目

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

要求返回这个链表的深拷贝。

示意图
示意图

示例：

1
2
3
4
5
6
输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

节点数据结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};

题目分析

其实我一开始没太看懂，所以题目特意用的中文版的。
大概意思就是，有这么一个链表，其中的节点不止有 next 指针，还有一个指向随机节点的 random 指针，要求我们复制一个它的深拷贝，即重新开辟一个空间，传值而不是传引用。

哈希表解题思路

代码1：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public Node copyRandomList(Node head) {

    if (head == null) return null;
    Map<Node, Node> map = new HashMap<>();

    // loop 1. copy所有节点
    RandomListNode cur = head;
    while (cur != null) {
        map.put(cur, new Node(cur.val, null, null));
        cur = cur.next;
    }

    // loop 2. 分配所有的指针( next 和 random )
    cur = head;
    while (cur != null) {
        map.get(cur).next = map.get(cur.next);
        map.get(cur).random = map.get(cur.random);
        cur = cur.next;
    }

    return map.get(head);
}

优化——常数空间复杂度

一个直观的解决方案是为列表中的每个节点保留一个哈希表，通过这个哈希表，我们只需要分别在两轮中迭代列表来创建节点并为它们的随机指针分配值。结果，这个解的空间复杂度是0(N)，尽管具有线性时间复杂度。

作为一个优化的解决方案，我们可以将空间复杂度降低到常数。想法是将原始节点与其副本节点关联在一个链接列表中。这样，我们不需要额外的空间来跟踪新节点。

该算法由以下三个步骤组成，也是三轮迭代。

迭代原始列表并复制每个节点。每个节点的副本会立即跟随其原始副本。迭代新列表，并为每个复制的节点分配随机指针。恢复原始列表并提取重复的节点。该算法实现图示如下:

示意图1
示意图1
示意图2
示意图2

代码2：常数空间复杂度

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
29
public Node copyRandomList(Node head) {
    if (head == null) return null;
    Node cur = head;
    //第一步：copy一份，并放在原版后面
    while (cur != null) {
        Node next = cur.next;
        cur.next = new Node(cur.val, next, null);
        cur = next;
    }
    //第二步：令copy的随机指针指向应该指向的copy
    cur = head;
    while (cur != null) {
        if (cur.random != null)
            cur.next.random = cur.random.next;
        cur = cur.next.next;
    }
    //第三步：把cpoy分离出来
    cur = head;
    Node copyHead = head.next;
    while (cur != null) {
        Node next = cur.next.next;
        Node copy = cur.next;
        cur.next = next;
        if (next != null)
            copy.next = next.next;
        cur = next;
    }
    return copyHead;
}

更多关于链表的问题

更多关于链表的问题请转到链表标签

更多关于哈希表的问题

更多关于哈希表的问题请转到链表标签