首页 技术 正文
技术 2022年11月9日
0 收藏 986 点赞 5,064 浏览 1008 个字

这题很是巧妙。

突破了常规思维。

竟然可以把传入进来的链表和复制的链表链在一起。然后再算出slibling指针。最后在分离。

直接把空间复杂度变为O(1)了。

很巧妙,很实用。

题目:

请实现函数ComplexListNode* Clone(ComplexListNode* pHead),复制一个复杂链表。

在复杂链表中,每个结点除了有一个pNext指针指向下一个结点之外,还有一个pSibling指向链表中的任意结点或者NULL。

结点的定义如下:

12345 struct ComplexListNode{    int val;    ComplexListNode* pNext;    ComplexListNode* pSibling;};

思路:

方法1:

复制原始链表上的每一个结点,并通过pNext连接起来;然后再设置每个结点的pSibling指针。

假设原始链表中某个结点N的pSibling指针指向结点S,那么就需要从头到尾遍历查找结点S,如果从原始链表的头指针开始,经过m步之后达到结点S,那么在复制链表中的结点N’的pSibling指针指向的结点也是距离复制链表s步的结点。通过这种办法就可以为复制链表上的每个结点设置pSibling指针。

时间复杂度:O(N^2)

方法2:

方法1是通过链表查找来得到pSibling指针所指向的结点,实际上我们可以通过空间换取时间,将原始链表和复制链表的结点通过哈希表对应起来,这样查找的时间就从O(N)变为O(1)。具体如下:

复制原始链表上的每个结点N创建N’,然后把这些创建出来的结点用pNext连接起来。同时把<N,N’>的配对信息方法一个哈希表中;然后设置复制链表中的每个结点的pSibling指针,如果原始链表中结点N的pSibling指向结点S,那么在复制链表中,对应的N’应该指向S’。

时间复杂度:O(N)

方法3:

在不使用辅助空间的情况下实现O(N)的时间效率。

第一步:根据原始链表的每个结点N创建对应的N’,然后将N‘通过pNext接到N的后面;

第二步:设置复制出来的结点的pSibling。假设原始链表上的N的pSibling指向结点S,那么其对应复制出来的N’是N->pNext指向的结点,同样S’也是结点S->pNext指向的结点。

第三步:把长链表拆分成两个链表,把奇数位置的结点用pNext连接起来的就是原始链表,把偶数位置的结点通过pNext连接起来的就是复制链表。

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/42506.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,071
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,505
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,317
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,311
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,911
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,099
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站