复制带随机指针的链表:奇妙的拷贝之旅

简介: 题目要求对一个带有随机指针的链表进行深拷贝,复制链表中的节点值、next 指针和 random 指针都应指向复制链表中的新节点。我们需要设计一个算法,满足这些条件,输入为原链表的头节点 head。

题目传送门

在本篇文章中,我们将解析题目 "复制带随机指针的链表",要求在给定一个带随机指针的链表的情况下,进行深拷贝并返回复制链表的头节点。我们将会探讨如何设计一个满足题目要求的算法,逐步展开这个问题的解决方案。


解析题意

题目要求对一个带有随机指针的链表进行深拷贝,复制链表中的节点值、next 指针和 random 指针都应指向复制链表中的新节点。我们需要设计一个算法,满足这些条件,输入为原链表的头节点 head。


奇妙思路

我们可以使用哈希表来建立原链表节点和复制链表节点的映射关系,这样在构建复制链表时就能方便地处理随机指针的拷贝。具体步骤如下:


第一遍遍历:创建复制链表的新节点,并将新节点和原节点的对应关系存入哈希表。

第二遍遍历:根据哈希表的映射关系,复制原链表节点的 next 和 random 指针。

代码实现

以下是用 C++ 实现复制带随机指针的链表的代码:

#include <unordered_map>


class Node {

public:

   int val;

   Node* next;

   Node* random;

   Node(int val) : val(val), next(nullptr), random(nullptr) {}

};


class Solution {

public:

   Node* copyRandomList(Node* head) {

       if (!head) return nullptr;


       std::unordered_map<Node*, Node*> nodeMap; // 原节点和复制节点的映射关系


       // 第一遍遍历:创建复制链表的新节点

       Node* curr = head;

       while (curr) {

           nodeMap[curr] = new Node(curr->val);

           curr = curr->next;

       }


       // 第二遍遍历:复制 next 和 random 指针

       curr = head;

       while (curr) {

           if (curr->next) {

               nodeMap[curr]->next = nodeMap[curr->next];

           }

           if (curr->random) {

               nodeMap[curr]->random = nodeMap[curr->random];

           }

           curr = curr->next;

       }


       return nodeMap[head];

   }

};

妙趣例证

假设原链表为:1 -> 2 -> 3 -> 4,且随机指针关系为 1.random 指向 3,2.random 指向 1,3.random 指向 4,4.random 指向 2。经过调用 copyRandomList 后,复制链表也会得到相应的复制节点以及对应的随机指针关系。


深入探索

这个问题中,利用哈希表的映射关系帮助我们在第二遍遍历时能够方便地找到复制链表中节点的对应关系。这个方法虽然使用了额外的空间,但确实是一个高效且易于理解的解决方案。


目录
相关文章
|
2月前
链表指针的传参,传值和传地址
本文讨论了链表操作中指针传参的问题,特别是指针的传值与传地址的区别,并提供了修正代码,以确保链表插入操作能正确地修改指针指向的地址。
17 1
链表指针的传参,传值和传地址
|
7月前
|
存储 C语言
用指针处理链表
用指针处理链表
62 3
|
2月前
|
存储
一篇文章了解区分指针数组,数组指针,函数指针,链表。
一篇文章了解区分指针数组,数组指针,函数指针,链表。
19 0
|
2月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
32 0
|
5月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
54 1
【数据结构OJ题】复制带随机指针的链表
|
4月前
|
Python
【Leetcode刷题Python】138. 复制带随机指针的链表
LeetCode上题目“138. 复制带随机指针的链表”的Python解决方案,包括两种方法:一种是在每个节点后复制一个新节点然后再分离出来形成新链表;另一种是构建一个字典来跟踪原始节点与其副本之间的映射关系,从而处理新链表的构建。
22 1
|
4月前
|
存储 算法 数据处理
指针与链表
指针与链表
74 0
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
7月前
|
存储 C语言
链表—初始化指针变和创建新的节点------区别应用分析
链表—初始化指针变和创建新的节点------区别应用分析
|
7月前
|
存储 缓存 搜索推荐
指针链表
指针链表
47 0