复制带随机指针的链表
本文最后更新于33 天前,其中的信息可能已经过时,如有错误请发送邮件到big_fw@foxmail.com

🔗 复制带随机指针的链表

题目来源:138. 随机链表的复制 – 力扣(LeetCode)

📌 题目描述

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random,该指针可以指向链表中的任何节点或空节点

要求你构造这个链表的深拷贝

  • 深拷贝应由 n 个全新节点组成,每个新节点的值等于原节点。
  • 新节点的 next 和 random 指针必须指向复制链表中的新节点
  • 不能指向原链表中的任何节点
  • 输入/输出以 [val, random_index] 形式表示,random_index 是目标节点的索引(0 到 n-1),若为 null 表示不指向任何节点。

✅ 示例解析

示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
解释:每个节点值复制,random 指针指向复制后链表中对应的新节点。

示例 2:

输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]
解释:节点1的random指向节点2,节点2的random也指向节点2(自身)。

示例 3:

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

⚠️ 提示

  • 0 <= n <= 1000
  • -10⁴ <= Node.val <= 10⁴
  • Node.random 为 null 或指向链表中的节点

💡 解法:哈希表映射法 —— O(n) 时间,O(n) 空间

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        // 第一步:遍历原链表,创建新节点并建立映射
        HashMap<Node, Node> map = new HashMap<>();
        Node p = head;

        while (p != null) {
            map.put(p, new Node(p.val));
            p = p.next;
        }

        // 第二步:再次遍历,设置新节点的 next 和 random
        p = head;
        while (p != null) {
            Node temp = map.get(p);
            temp.next = map.get(p.next);   // 新节点的 next 指向对应新节点
            temp.random = map.get(p.random); // 新节点的 random 指向对应新节点
            p = p.next;
        }

        // 第三步:返回新链表头节点
        return map.get(head);
    }
}

📊 复杂度分析

  • 时间复杂度:O(n)
    • 两次遍历链表,每次 O(n),哈希表操作平均 O(1)。
  • 空间复杂度:O(n) ✅
    • 使用哈希表存储 n 个节点映射关系。

🧩 解题思路

核心思想:两次遍历 + 哈希表建立原节点与新节点的一一映射

  1. 边界处理:
    • 若 head == null,直接返回 null
  2. 第一次遍历 —— 创建节点并建立映射:
    • 遍历原链表每个节点 p
    • 为每个 p 创建一个新节点 new Node(p.val)
    • 存入哈希表 map.put(p, newNode) → 建立“旧节点 → 新节点”的映射。
  3. 第二次遍历 —— 设置指针关系:
    • 再次从头遍历原链表。
    • 对每个原节点 p
      • 获取对应新节点 temp = map.get(p)
      • 设置 temp.next = map.get(p.next) → 若 p.next 为 null,则返回 null
      • 设置 temp.random = map.get(p.random) → 同理,支持 null
    • 完成所有新节点的连接。
  4. 返回结果:
    • map.get(head) 即为复制链表的头节点。
文末附加内容
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇