LeetCode 第 138 题:复制带随机指针的链表(Python 代码)

简介: 给定一个长度为 n 的链表,每个节点比普通的节点多了一个额外的随机指针 ramdom,该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。所谓的深拷贝,就是完全生成一个新的对象,内存地址都是不同的,这样改变拷贝之前变量,就不会影响到拷贝的变量。

题目 138. 复制带随机指针的链表 的描述如下,给定一个长度为 n 的链表,每个节点比普通的节点多了一个额外的随机指针 ramdom,该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。所谓的深拷贝,就是完全生成一个新的对象,内存地址都是不同的,这样改变拷贝之前变量,就不会影响到拷贝的变量。

哈希映射 1

首先贴一个比较巧妙的解法,来自用户 skyliuhc,在官方题解下面的评论可以看到,他写的是 Java 的版本,这里我写成 Python 的版本:

主要的思路就是,先用一个循环把新旧链表对应的两个结点捆绑在一个二元组里,然后再用一个循环完成对新链表每个结点的 nextrandom 的赋值

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        cur = head
        hashmap = {}  # 哈希表
        # 第一个循环,建立映射
        while cur:
            hashmap[cur] = Node(cur.val)  # 新旧链表对应结点映射
            cur = cur.next  # 当前结点往后移动
        # 第二个循环,next 和 random 赋值
        cur = head
        while cur:
            # 因为 Python 的字典中不能用 None 作为键值,所以要做一个特殊判断
            hashmap[cur].next = hashmap[cur.next] if cur.next else None
            hashmap[cur].random = hashmap[cur.random] if cur.random else None
            cur = cur.next
        return hashmap[head]

哈希映射 2

这个是我自己当时做题的时候想的方法,与前面一个的想法类似,也是打算用哈希表来记录新旧链表的结点,但是想法更为复杂了,具体的思路为:

  • 1、先把最普通的链表构建起来,同时记录两个 Hashmap

    • 1.1、Node2Pos:旧链表的每个 Node 的位置
    • 1.2、Pos2Node:新链表每个位置对应的 Node
  • 2、同步遍历新旧两个链表,得到当前位置的旧节点的 random node 对应的位置 pos
  • 3、通过位置 pos 得到新链表的 Node,就知道当前结点的 random 要指向哪里;
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        Node2Pos = {}  # 旧链表的每个 `Node` 的位置
        Pos2Node = {}  # 新链表每个位置对应的 `Node`
        # 构建新链表
        newPreHead = Node(0)  # 前置结点
        new_ptr = newPreHead  # 新链表的头结点
        old_ptr = head  # 旧链表的头结点 
        idx = 0 # 当前的位置
        while old_ptr: 
            Node2Pos[old_ptr] = idx  # 记录旧结点位置
            new_ptr.next = Node(old_ptr.val)
            new_ptr = new_ptr.next
            Pos2Node[idx] = new_ptr  # 记录当前位置的新结点
            idx += 1  # 位置也要同步往后
            old_ptr = old_ptr.next
        Pos2Node[idx] = None  # 最后一个位置是空指针 None
        
        # 处理 random node
        new_ptr = newPreHead.next
        old_ptr = head
        while old_ptr:
            random_node = old_ptr.random  # 获得旧结点的随机结点
            # 获得旧结点随机结点的位置,如果为随机结点为空代表是最后一个位置,即 idx
            pos = Node2Pos[random_node] if random_node else idx
            node = Pos2Node[pos]  # 获得对应 pos 的结点
            new_ptr.random = node
            new_ptr = new_ptr.next
            old_ptr = old_ptr.next
        
        return newPreHead.next  # 返回结果

回溯 + 哈希表

官方题解:利用回溯法,让每个节点的拷贝操作相互独立,对于当前结点,首先进行拷贝,然后进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝,拷贝完成后将创建的新节点的指针返回,即可完成当前节点的两指针的赋值。

具体的做法是:

  • 先创建一个哈希表 cachedNode,从头结点开始遍历;
  • 如果结点为空,返回 None
  • 创建一个新的结点,其值与当前遍历的结点值 val 一样;
  • 然后遍历地去对 nextrandom 赋值;
class Solution:
    def __init__(self,):
        self.cachedNode = {}
    
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        if head not in self.cachedNode.keys():
            headNew = Node(head.val)  # 拷贝新节点
            self.cachedNode[head] = headNew  # 记录到哈希表中
            headNew.next = self.copyRandomList(head.next)
            headNew.random = self.copyRandomList(head.random)
        return self.cachedNode[head]

迭代 + 节点拆分

  • 对于链表 A => B => C,可以将其变成 A => A' => B => B' => C => C',其中 A'A 的拷贝结点
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        # 将 A => B 变成 A => A' => B => B'
        node = head
        while node:
            nodeNew = Node(node.val)
            nodeNew.next = node.next
            node.next = nodeNew
            node = node.next.next
        
        # 处理 random
        node = head
        while node:
            nodeNew = node.next
            nodeNew.random = node.random.next if node.random else None
            node = node.next.next
            
        # 将 A => A' => B => B' 变成 A => B
        headNew = head.next
        node = head
        while node:
            nodeNew = node.next
            node.next = node.next.next
            nodeNew.next = nodeNew.next.next if nodeNew.next else None
            node = node.next
        
        return headNew
目录
相关文章
|
5月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
59 1
|
5月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
81 0
Leetcode第21题(合并两个有序链表)
|
1月前
|
存储 Python
Python 实现单向链表,和单向链表的反转
链表是一种数据结构,每个节点存储相邻节点的位置信息。单链表中的节点仅存储下一节点的位置。通过Python实现单链表,定义`ListNode`类并关联节点可创建链表。例如,创建A->B->C的链表后,可通过反转函数`reverse`将链表反转为CBA。代码展示了如何实现和操作单链表。
Python 实现单向链表,和单向链表的反转
|
1月前
|
存储 算法 搜索推荐
Python 实现反转、合并链表有啥用?
大家好,我是V哥。本文介绍Python实现反转链表和合并链表的应用场景及代码实现。反转链表适用于时间序列数据展示、回文链表判断等;合并链表则用于大规模数据排序、数据库查询结果集合并等。通过迭代和递归方法实现反转链表,以及合并两个或多个有序链表的算法,帮助开发者解决实际问题。关注V哥,了解更多实用编程技巧。 先赞再看后评论,腰缠万贯财进门。
|
3月前
|
算法 容器
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
|
2月前
|
Python
探索 Python 中链表的实现:从基础到高级
链表是一种由节点组成的基础数据结构,每个节点包含数据和指向下一个节点的引用。本文通过Python类实现单向链表,详细介绍了创建、插入、删除节点等操作,并提供示例代码帮助理解。链表在处理动态数据时具有高效性,适用于大量数据变动的场景。文章为初学者提供了全面的入门指南,助你掌握链表的核心概念与应用。
104 0
|
5月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
54 0
LeetCode第二十四题(两两交换链表中的节点)
|
5月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
63 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
5月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
136 0
|
算法 Python
<LeetCode天梯>Day026 反转链表(递归法+(迭代法)双链表法) | 初级算法 | Python
<LeetCode天梯>Day026 反转链表(递归法+(迭代法)双链表法) | 初级算法 | Python
<LeetCode天梯>Day026 反转链表(递归法+(迭代法)双链表法) | 初级算法 | Python