目录

【算法】复制带随机指针的链表

题目描述

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

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

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

val:一个表示 Node.val 的整数。 random_index:随机指针指向的节点索引(范围从 0n-1);如果不指向任何节点,则为 null

 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;
    }
}

示例 1

https://leslie-cloud.oss-cn-beijing.aliyuncs.com/2021/01/copy-linklist-with-random-pointer-e1.png

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

示例 2

https://leslie-cloud.oss-cn-beijing.aliyuncs.com/2021/01/copy-linklist-with-random-pointer-e2.png

1
2
输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]

示例 3

https://leslie-cloud.oss-cn-beijing.aliyuncs.com/2021/01/copy-linklist-with-random-pointer-e3.png

1
2
输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

示例 4

1
2
3
输入:head = []
输出:[]
解释:给定的链表为空(空指针),因此返回 null。

提示:

  • -10000 <= Node.val <= 10000
  • Node.random 为空(null)或指向链表中的节点。
  • 节点数目不超过 1000 。

作者:力扣 (LeetCode)

链接:LeetCode - 算法面试题汇总

来源:力扣 (LeetCode)

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

问题抽象

输入

1
2
3
4
A-->B-->C-->D	---1
|	|	|	|	---2
|	C	A	|
null		null

输出

1
2
3
4
A'->B'->C'->D'	---1'
|	|	|	|	---2’
|	C'	A'	|
null		null

解题思路

如果是没有随机指针的链表,直接使用一个简单的遍历-拷贝的操作就可以解决这个问题,加上一个随机指针后,我们还需要将随机指针指向复制链表的对应结点,这就在原有问题的基础上提升了一些难度。

我将这个问题分两步解决,第一步是从链表 head深拷贝 val 实例,浅拷贝** random 实例,得到链表 ans ,此时 ans 中的 random 实例指向的是链表 head 中的结点,第二步只需要修改 random 实例指向对应的 ans 中的相应结点即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
------------------------------1------------------------------
Before:	A-->B-->C-->D	---1	After:	A'->B'->C'->D'	---1'
		|	|	|	|	---2			|	|	|	|   ---2
		|	C	A	|					|	C	A	|
		null		null				null		null
------------------------------2------------------------------
Before:	A-->B-->C-->D	---1	After:	A'->B'->C'->D'	---1'
		|	|	|	|	---2			|	|	|	|   ---2‘
		|	C	A	|					|	C‘	A’	|
		null		null				null		null
------------------------------------------------------------

第一步很简单,直接遍历就可以做到。

1
2
3
4
5
6
7
Node ans = new Node(head.val);	// 深拷贝
ans.random = head.random;		// 浅拷贝

while (head.next != null) {
	ans.next = new Node(head.next.val);	// 深拷贝
    ans.next.random = head.next.random; // 浅拷贝
}

简单观察后可以发现,第二步只需要保存 C->C' A->A' 的映射,然后修改复制链表的 random 指针,这就转换成了Key->Value 的问题,只需要简单添加一个哈希表就可以解决。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
HashMap<Node, Node> originToCopy = new HashMap<>(1000);
Node ans = new Node(head.val);	// 深拷贝
ans.random = head.random;		// 浅拷贝
originToCopy.put(head, ans);	// 保存 origin->copy 的映射

while (head.next != null) {
    ans.next = new Node(head.next.val);	// 深拷贝
    ans.next.random = head.next.random; // 浅拷贝
    originToCopy.put(head, ans);		// 保存 origin->copy 的映射
    head = head.next;
    ans = ans.next;
}

最后遍历链表 ans 修改 random 实例:

1
2
3
4
while (ans != null) {
	ans.random = originToCopy.get(ans.val);	// 修改 random 实例
    ans = ans.next;
}

整理一下代码,解决边界问题,全部代码如下:

 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
30
31
public static Node copyRandomList(Node head) {
    // 如果链表为空,直接返回 null
    if (head == null) return null;

    HashMap<Node, Node> originToCopy = new HashMap<>(1000);
    Node ans = new Node(head.val);	// 深拷贝
    ans.random = head.random;		// 浅拷贝
    originToCopy.put(head, ans);	// 保存 origin->copy 的映射

    // 固定 head 和 ans,用 p, q 作为游标移动
    Node p = head;
    Node q = ans;

    while (p.next != null) {
        q.next = new Node(p.next.val);		// 深拷贝
        q.next.random = p.next.random;		// 浅拷贝
        originToCopy.put(p.next, q.next);	// 保存 origin->copy 的映射
        p = p.next;
        q = q.next;
    }

    q = ans;

    while (q != null) {
        // random 实例为空直接跳过,有值则修改指针
        if (q.random != null) q.random = originToCopy.get(q.random);
        q = q.next;
    }

    return ans;
}