[python 刷题] 138 Copy List with Random Pointer

[python 刷题] 138 Copy List with Random Pointer

题目：

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

这道题目说起来很复杂，实际上还是挺简单的，主要就是说让创建一个深拷贝（也就是说二者内存地址并不想通的复制）。

除了深拷贝之外，这道题还有一个比较特殊的点，一般的单链表里每个结点只有 next，指向下一个结点的地址。这里除了有 next 这个指针外，还有一个 random 的指针，指向链表中任一一个结点。

最简单的实现方法是跑两遍循环，第一个循环将所有的元素存到哈希表中，第二个循环则完成 random 和 next 指向的实现。

代码如下：

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return head

        d = {}

        t = head
        while t:
            d[t] = Node(t.val)
            t = t.next

        t = head
        while t:
            d[t].next = d.get(t.next)
            d[t].random = d.get(t.random)
            t = t.next

        return d[head]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这里有两个点需要注意的地方：

1. 字典中的 key 中需要保存的是单独的结点：

   key	value
   Node	Node

   题目中并没有说过所有的元素都具有唯一性，因此也有可能存在两个结点的 val 是同一个值的情况

2. 对于空值 None 的处理

   这里用 d[t.next] 会报错，原因是因为第一个循环里走的是 while t:，当找到最后一个结点时，t.next 的值为 None，dict 中没有 None 的值就会报错

   处理方式有两个：

   • 第一个是使用 d.get()，这样字典在不存在 key 时不会报错，而是会返回默认值，或者在这个情况下，没有提供默认值则为 None
   • 初始化的时候添加一个 None 值：d: {None: None}

这道题用 one-pass 也可以实现，代码如下：

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        d = {}

        new_head = Node(0)
        prev = new_head

        l = 0

        while head:
            if head not in d:
                d[head] = Node(head.val)
            prev.next = d[head]

            if head.random:
                if head.random not in d:
                    d[head.random] = Node(head.random.val)

                d[head].random = d[head.random]

            prev = prev.next
            head = head.next


        return new_head.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

处理方式和 2-pass 实现差不多，我跑了一下，用 1-pass 并没有快很多，不过实现起来会稍微麻烦一些是真的