LeetCode刷题--- 138. 复制带随机指针的链表(哈希表+迭代)

简介: LeetCode刷题--- 138. 复制带随机指针的链表(哈希表+迭代)



一、编程题:430. 扁平化多级双向链表(双指针)

1.题目描述

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

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

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

  返回复制链表的头节点。

  用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。

  你的代码 只 接受原链表的头节点 head 作为传入参数。LeetCode题目链接。

2.示例1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

3.示例2:

输入:head = [[1,1],[2,1]]

输出:[[1,1],[2,1]]

4.示例3:

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

输出:[[3,null],[3,0],[3,null]]

5.提示:

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

二、解题思路

1. 题目分析

  这里主要参考了三叶姐和官方题解提供的思路,非常感谢这些大佬。🌹 🌹 🌹

  题目要求我们对一个特殊的链表进行深拷贝。这里就需要注意两点了:

  • 在拷贝结束后,不能改变原链表的结构,也是说拷贝过程中可以修改,但结束之后需要还原回去;
  • 在拷贝节点时,因为随机指针指向的节点可能还没创建,所以只能先建立拷贝链表,再来完成随机指针的赋值;

2. 方法1(哈希表)

思路:
  • Step 1.将原节点进行复制,在采用哈希表构建原节点和新节点的映射关系;
  • Step 2.对原链表进行遍历,原链表节点上的nextrandom可以通过哈希表查询到对应的新节点,根据其操作给新节点的nextrandom指针进行赋值;
  • Step 3.重复2步骤,直到原链表遍历完时循环终止,并返回新链表头节点;

看不懂解释的话,直接看算法图解比较容易理解点

复杂度分析:

时间复杂度:O(n),其中 n 是链表的长度。对于每个节点,我们至多访问其「后继节点」和「随机指针指向的节点」各一次,均摊每个点至多被访问两次。

空间复杂度:O(n),其中 n 是链表的长度。为哈希表的空间开销。

算法图解

哈希表,红色部分代表新建立节点,灰色部分代表原链表节点;(注:本人不会做成流程动画,希望会的朋友可以私信我指点一二,说个软件名字也可以,谢谢

3. 方法二:迭代

  方法一使用哈希表就为了构建原节点和新节点和映射关系,能快速查询每个节点。但也可以不用哈希表进行构建其映射关系;

  在解题过程中我们想要的是原节点和新节点的映射关系,所以将新节点复制在原节点后面,从而构建出其映射关系;

思路:
  • Step 1.对原节点进行复制并将其拼接该节点后面;
  • Step 2.创建好新节点后,可以发现链表中的偶数位置代表原节点,奇数位置代表了新节点(注意:这里是从0开始数起的),每个原节点的next指针都对应着新节点;
  • Step 3.对链表进行遍历,通过计算list[i].random = list[i-1].random.next构建新节点的random指针,其中i为偶数下标,list[i-1]意思是新节点前面的那个原节点;
  • Step 4.重复3步骤,直到原节点遍历完时循环终止,还需要对链表进行拆分再返回新链表头节点;

看不懂解释的话,直接看算法图解比较容易理解点

复杂度分析:

时间复杂度:O(n),其中 n 是链表的长度。我们只需要遍历该链表三次。

空间复杂度:O(1)。注意返回值不计入空间复杂度。

算法图解

  红色部分代表原节点,灰色部分代表新节点,蓝色部分为当前遍历的节点;(注:本人不会做成流程动画,希望会的朋友可以私信我指点一二,说个软件名字也可以,谢谢

  • 复制新节点

  • 构建新节点random关系

  • 拆分链表


三、代码实现

每个代码块都写了注释,方便理解,代码还可以改进;

方法一:哈希表

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node p = head, q;
        while(p != null){
            q = new Node(p.val);
            map.put(p,q);
            p = p.next;
        }
        p = head;
        q = map.get(p);
        // 通过散列表特性加快查询速度
        while(p != null){
            q.next = map.get(p.next);
            q.random = map.get(p.random);
            q = q.next;
            p = p.next;
        }
        return map.get(head);
    }
}

提交结果:

方法二:迭代

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return head;
        Node first = head, temp;
        // 复制链表,将当前节点复制在节点后面
        while(first != null){
            temp = new Node(first.val);
            temp.next = first.next;
            first.next = temp;
            first = temp.next;
        }
        // 构建节点random关系
        first = head;
        while(first != null){
            if(first.random != null) first.next.random = first.random.next;
            first = first.next.next;
        }
        // 拆分链表
        first = head;
        Node second = head.next;
        while(first != null){
            Node temp_second = first.next;
            if(temp_second != null) first.next = temp_second.next;
            first = temp_second;
        }
        return second;
    }
}

提交结果:


总结

以上就是今天要讲的内容,这一题还是比较容易被题意误导的,一开始我就改变了原链表的结构导致出错,后面看了各位大佬的题解就突然恍然大悟了。

感谢观看,如果有帮助到你,请给题解点个赞和收藏,让更多的人看到。🌹 🌹 🌹

也欢迎你,关注我。👍 👍 👍

原创不易,还希望各位大佬支持一下,你们的点赞、收藏和留言对我真的很重要!!!💕 💕 💕 最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!


相关文章
|
1天前
|
算法 索引
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
|
1天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣82
【数据结构与算法 | 基础篇】[链表专题]力扣82
|
1天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣21, 234
【数据结构与算法 | 基础篇】[链表专题]力扣21, 234
|
1天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣LCR077, 83
【数据结构与算法 | 基础篇】[链表专题]力扣LCR077, 83
|
1天前
|
存储 算法
【数据结构与算法 | 基础篇】[链表专题]力扣206, 203, 19
【数据结构与算法 | 基础篇】[链表专题]力扣206, 203, 19
|
8天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
12 0
|
8天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
16 0
|
8天前
|
算法
【刷题】 leetcode 面试题 08.05.递归乘法
递归算法是一种在计算机科学和数学中广泛应用的解决问题的方法,其基本思想是利用问题的自我相似性,即将一个大问题分解为一个或多个相同或相似的小问题来解决。递归算法的核心在于函数(或过程)能够直接或间接地调用自身来求解问题的不同部分,直到达到基本情况(也称为基础案例或终止条件),这时可以直接得出答案而不必再进行递归调用。
28 4
【刷题】 leetcode 面试题 08.05.递归乘法
|
8天前
|
存储 算法 安全
【刷题】 leetcode 面试题 01.06 字符串压缩
来看效果: 非常好!!!过啦!!!
30 5
【刷题】 leetcode 面试题 01.06 字符串压缩

热门文章

最新文章