0138：随机链表的复制（★）

2015-05-18 约 741 字预计阅读 2 分钟次阅读

力扣第 138 题

题目

给你一个长度为 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：

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

示例 2：

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

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-10⁴ <= Node.val <= 10⁴
Node.random 为 null 或指向链表中的节点。

分析

类似 0133，可以用哈希表加 dfs。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        def dfs(u):
            if not u:
                return None
            d[u] = Node(u.val)
            d[u].next = d[u.next] if u.next in d else dfs(u.next)
            d[u].random = d[u.random] if u.random in d else dfs(u.random)
            return d[u]
        d = {}
        return dfs(head)

34 ms

*附加

本题还有个非常巧妙的方法，不用额外空间。

先将新节点 new 依次插入到原节点 old 的后面
那么 old.random.next 就应该是 new.random
最后再按顺序拆分出新节点，即调整 next 的指向

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


class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        p = head
        while p:
            p.next = Node(p.val, p.next)
            p = p.next.next
        p = head
        while p:
            p.next.random = p.random.next if p.random else None
            p = p.next.next
        p = head
        dum = q = Node(0)
        while p:
            q.next = p.next
            p.next = p.next.next
            p = p.next
            q = q.next
        return dum.next

32 ms

目录

0138：随机链表的复制（★）

题目

分析

解答

*附加