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

Leetcode
1.2k 词

我们用哈希表来解决这个问题
首先创建一个哈希表，再遍历原链表，遍历的同时再不断创建新节点
我们将原节点作为key，新节点作为value放入哈希表中

image.png

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
"""

# Definition for a Node.

class Node:

    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):

        self.val = int(x)

        self.next = next

        self.random = random

"""

  

class Solution:

    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':

        if not head:  # 关键补充

            return None

        d=dict()

        p=head

        while p:

            new_node=Node(p.val,None,None)

            d[p]=new_node

            p=p.next

        p=head

        while p:

            if p.next:

                d[p].next=d[p.next]

            if p.random:    

                d[p].random=d[p.random]

            p=p.next

        return d[head]

第一次循环（建映射，创建“影子节点”）

  • p 是原链表的当前节点（原节点对象）

  • 在字典 d 中：

    • key = p（原节点的引用）

    • value = Node(p.val, None, None)（一个新建节点对象的引用）

  • 此时新建节点的 next 和 random 都是 None，所以这些新节点是“孤立点”

例子：
原链表： A → B → C
哈希表：

1
2
3
d[A] = A'(next=None, random=None)
d[B] = B'(next=None, random=None)
d[C] = C'(next=None, random=None)

第二次循环（接指针，补全结构）

  • 目的：把 d[p]（新节点）内部的 next / random 指针补好

  • 补 next：

    • 原链表： p.next 是原节点的下一个

    • 新链表： d[p].next 应该指向 d[p.next]（下一个原节点对应的新节点）

  • 补 random：

    • 原链表： p.random 是原节点的随机指向

    • 新链表： d[p].random 应该指向 d[p.random]（原节点随机指向对应的新节点）

例子（假设 A.random → C）：
第二次循环后：

1
2
3
A'.next = B'
B'.next = C'
A'.random = C'

这样，新链表的节点之间关系和原链表完全一致，但对象是全新的。