目录

0138:随机链表的复制(★)

力扣第 138 题

题目

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

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

例如,如果原链表中有 XY 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 xy ,同样有 x.random --> y

返回复制链表的头节点。

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

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0n-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
  • -104 <= Node.val <= 104
  • Node.randomnull 或指向链表中的节点。

相似问题:

分析

类似 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