关于数据结构与算法:每日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]

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理