关于数据结构与算法:每日leetcode138-复制带随机指针的链表

给你一个长度为 n 的链表，每个节点蕴含一个额定减少的随机指针 random，该指针能够指向链表中的任何节点或空节点。

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

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

返回复制链表的头节点。

感觉这道题的难点，在于读懂题目说的啥 …
其实题目的意思就是：
有一个链表，这个链表的节点，不光有 next 指针，还有一个 random 指针，随机指向某个节点或是 None。当初让你复制一份这个链表。

def copyRandomList(head):
    if not head:
        return None
    
    # 设置一个字典
    dic = {}
    # 头节点处初始化一个指针 cur
    cur = head
    # 第 1 遍遍历链表的每个节点
    while cur!=None:
        # 以后节点作为 key，以后节点的 copy 节点作为 val，存入字典中
        dic[cur] = Node(cur.val)
        # 挪动指针，持续下一个节点
        cur = cur.next
    
    # 第 1 遍遍历实现后，每个节点都复制了一份
    # cur 再放回到表头处
    cur = head
    # 第 2 遍遍历，为 copy 节点进行 next 和 random 指针的链接
    while cur!=None:
        # copy 节点的 next 指向原节点的 next 的 copy
        dic[cur].next = dic[cur.next] if cur.next else None
        # copy 节点的 random 指向原节点的 next 的 random
        dic[cur].random = dic[cur.random] if cur.random else None
        # 挪动指针，持续下一个节点
        cur = cur.next

    # 返回头节点的 copy，即复制链表的头节点
    return dic[head]

题目

思路