Python | Leetcode Python题解之第138题随机链表的复制

题目：

题解：

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        allNode=[] # 用一个数组存储所有结点
        cur1=head
        while cur1:
            allNode.append(cur1)
            cur1=cur1.next
        n=len(allNode)
        allRandom=[-1]*n # 用一个数组存储所有节点的random指向的结点下标(下标-1表null)
        for i in range(n):
            randomNode=allNode[i].random
            if not randomNode:
                continue
            for j in range(n):
                if randomNode==allNode[j]:
                    allRandom[i]=j
                    break
        dummy=Node(0)
        cur2=dummy
        for i in range(n):# 创建n个新节点存储在原allNode数组中
            newnode=Node(allNode[i].val)
            allNode[i]=newnode
        for i in range(n):# 将n个新节点串联起来
            cur2.next=allNode[i]
            cur2=cur2.next
            if allRandom[i]!=-1:
                cur2.random=allNode[allRandom[i]]
        return dummy.next