Leetcode 138.复制带随机指针的链表

Leetcode

链表

发布日期: 2023-09-14

更新日期: 2023-09-14

文章字数: 1.2k

阅读时长: 4 分

阅读次数:

Leetcode 138. 复制带随机指针的链表

最近的编译原理课程的lab1进行了链表的基本操作，这下回来想着如果链表的指针并不唯一指定的话，需要怎么进行复制，或者说是链接。刚好在力扣找到了这道题，所以拿来试试手…

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 作为传入参数。

示例 1：

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

2. 解答分析

本题的基本操作是将链表进行复制，但是对于每个链表的节点而言都存在随机的指针random，其实在不考虑random指针的情况下，只需要将原先的链表进行拷贝，这里引入两个指针，一个用于遍历原链表，一个用于构造新链表（始终指向新链表的尾部）。

这个过程实际上就是创建节点+构建next的指针关系
所以现在就是在原先的基础上添加特定的random指针，我们可以将next指针和random指针进行关系的构建，从输入的格式中可以强烈看出应该是要用到哈希表的数据结构，key为原节点，对应的value是新节点。
- 先不考虑random指针的关系，和原本链表复制一样，创建新节点，并构造出next的指针关系，同时使用的是哈希表记录原节点和新节点的映射关系
- 对原链表和新链表进行同时遍历，对于原链表的每个节点上的random都利用哈希表的找到新random节点，并在新链表上构造random关系。也就是总共两条链表，其中的每个节点都是利用HashMap构造的对应映射关系

3. 具体代码

Java代码：

class Solution{
    public Node copyRandomList(Node head){
        Node t=head;
        Node dummy=new Node(-10010),cur=dummy;//dummy是空节点，cur是对应的指针
        Map<Node,Node>map=new HashMap<>();
        //第一次遍历原链表：遍历每个原节点 head，创建一个新节点 node 并保存到哈希表中，同时将新节点连接到复制链表中。(存HashMap)
        while(head!=null){
            Node node=new Node(head.val);
            map.put(head,node);
            cur.next=node;
            cur=cur.next;
            head=head.next;
        }
        
        cur=dummy.next;//重置指针
        head=t;//为第二次遍历做准备
        //第二次遍历原链表：遍历每个原节点 head，从哈希表中获取对应的复制节点，并将其赋值给复制链表当前节点的 random 指针。（进行链表复制）
        while(head!=null){
            cur.random=map.get(head.random);
            cur=cur.next;
            head=head.next;
        }
        return dummy.next;//返回复制指针的头节点
    }
}

复杂度分析
- 时间复杂度： $O(N)$
  
  两次遍历原链表：需要遍历整个链表，时间复杂度为 O(N)，其中 N 是原链表的长度。综上所述，总的时间复杂度为 O(N)。
- 空间复杂度： $O(N)$
  
  创建了一个哈希表 map，存储了原节点和对应的复制节点，因此需要额外的空间来存储哈希表中的键值对。哈希表的空间复杂度为 O(N)。同时为了复制链表，创建了哨兵节点dummy和指针cur,但是他们的数量和键值对数量一样为N，综上所述：空间复杂度为O(N)。