复杂链表的复制（python）_复杂链表的复制 python_Und.的博客-程序员秘密

一：问题描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

二：分析
1 明确输入输出
输入：一个复杂链表
输出：拷贝链表的头结点
2 名词解释
简单来说
深拷贝deepcopy：我们寻常意义的复制就是深复制，即将被复制对象完全再复制一遍作为独立的新个体单独存在。所以改变原有被复制对象不会对已经复制出来的新对象产生影响。
浅复制：并不会产生一个独立的对象单独存在，他只是将原有的数据块打上一个新标签，所以当其中一个标签被改变的时候，数据块就会发生变化，另一个标签也会随之改变。这就和我们寻常意义上的复制有所不同了。

我们的题目要求我们实现这么一个深复制，那么要怎么实现呢？

举个栗子：有链表pHead如下，他有两个指针。一个指向下一个节点，另一个特殊指针random指向一个随机节点，在这里我们假设random的指向如图所示：其中，3指向他自己。
在这里插入图片描述
第一步：

我们先复制一个node出来，然后将这个node合并到原链表中，接着通过while循环将原链表中的所有node复制出来，并建立连接

在这里插入图片描述
让新节点的next指针指向第二个旧结点

让第一个旧结点的next指针指向新节点，至此完成了一个结点的复制与连接，接下来对其他结点也做相同的事

继续跑while循环

paopaopao…
直到kk指向None，跳出循环。
至此，完成了所有结点的复制和next指针的相互连接

在这里插入图片描述
第二步

接下来复制random指针，这里用虚线表示random指针
在这里插入图片描述
旧结点1的random指向的是旧结点5，我们让新节点1的random指向旧5的下一个结点，也就是新结点5

旧3指向的是他自己，我们让新3指向旧3的下一个结点，也就是新3

这样，我们就复制好了所有的random指针（此处漏画了新node7的random）
在这里插入图片描述
第三步：要分离两个链表，在这里，我们定义了三个指针kk，ee和NN

ee指向的是新结点的表头，一会返回的也是ee
kk在旧结点上跑
NN在新链表上跑
他两负责切断新指向旧，旧指向新的next指针，并让next指针指到合适的位置
我们让新1的next指向新3
让旧1的next指向旧3
在这里插入图片描述
以此类推，直到成功分离两个链表

在这里插入图片描述
至此，已完全分离两个一摸一样的复杂链表，最后输出指针ee所指的表头对应的链表

完成

三，代码
在这里插入图片描述

本文链接：https://blog.csdn.net/slove3366/article/details/106686412

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

apk反汇编工具apktool问题之DexBackedDexFile$NotADexFile_rgwu的博客-程序员秘密

apktool反编apk时报错org.jf.dexlib2.dexbacked.DexBackedDexFile$NotADexFile: Not a valid dex magic value: cf 77 4c c7 9b 21 01 cd提示很明显，就是非法Dex，这是因为apk里有加密过后的dex文件，比如有些apk的assets目录下有加密后的Dex文件，添加–only-main-...

c++---string类的使用_boke_fengwei的博客-程序员秘密

string容器的基本概念string容器的常用操作string小小练习string容器的基本概念c风格字符串(以空字符结尾的字符数组)太过于复杂难于掌握，不太适合大程序的开发，c++在标准库定义一种string类，定义在头文件中- string和c风格字符串对比char是一个指针，string是一个类，string封装了char,管理这个字符串，是一个char型的容器。str...

[ACM_数学] 大菲波数 (hdu oj 1715 ,java 大数）_weixin_34375233的博客-程序员秘密

大菲波数Problem DescriptionFibonacci数列，定义如下：f(1)=f(2)=1f(n)=f(n-1)+f(n-2) n&gt;=3。计算第n项Fibonacci数值。 Input输入第一行为一个整数N，接下来N行为整数Pi（1&lt;=Pi&lt;=1000）。 Output输出为N行，每行为对应的f(Pi)。 Sample Inpu...

STM32简单的串口控制灯的亮灭_小王同志9527的博客-程序员秘密

STM32简单的串口控制灯的亮灭描述通过串口给开发板发送一串字符，来控制灯的亮灭，密码错误则报警串口初始化#if EN_USART1_RX //如果使能了接收//串口1中断服务程序//注意,读取USARTx->SR能避免莫名其妙的错误 u8 USART_RX_BUF[USART_REC_LEN]; //接收缓冲,最大USART_REC_LEN个字节.//接收状态//bit15，接收完成标志//bit14，接收到0x0d//bit13~0，接收到的有效字节

linux使用xshell远程上传文件_linux系统通过xshell上传文件_鱼大虾的博客-程序员秘密

1.安装服务yum -y install lrzsz2.上传命令:rz 选择文件进行上传即可.上传的文件默认保存linux当前所在目录3.下载命令:sz

nginx+uwsgi+django+python环境部署文档_django分布式部署_KISSING_hu的博客-程序员秘密

nginx+uwsgi+django+python环境部署文档为获得更好的阅读效果，请下载本文PDF文档：python+django+nginx+uwsgi环境部署文档下载地址：http://www.linuxyw.com/download/python_django_nginx_uwsgi.pdf环境：系统：Centos