复杂链表的复制
发布日期:2021-06-30 19:56:22
浏览次数:2
分类:技术文章
本文共 1414 字,大约阅读时间需要 4 分钟。
题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
题目链接:
分析:
注意,原来的链表也要分离出来,虽然不是题目要求,但是既然是复制,肯定是要额外的一条链表,不能破坏原来链表。
AC代码:
/*public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; }}*/public class Solution { public RandomListNode Clone(RandomListNode pHead) { if (pHead == null) return null; RandomListNode p = pHead; while (p != null) { RandomListNode node = new RandomListNode(p.label); node.next = p.next; p.next = node; p = node.next; } p = pHead.next; RandomListNode last = pHead; while (p != null) { // 可能random指向自己,或者一个不在链表中的结点 p.random = last.random == null ? null : last.random.next; last = p.next; p = last == null ? null : last.next; } RandomListNode curHead = pHead.next; last = pHead; p = curHead; while (p!= null) { last.next = p.next; last = p.next; p.next = last == null ? null : last.next; p = p.next; } return curHead; }}
测试点可能为{1,2,3,4,5,3,5,#,2,#} ,#代表null,链表可能1-2-3-4-5-3-5,#,2,#,这3个结点可能是非链表结点,但是是random指向的结点。
========================Talk is cheap, show me the code=======================
转载地址:https://liuchenyang0515.blog.csdn.net/article/details/85079212 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月09日 10时34分33秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
ACM路上的一大失误
2019-04-30
HDOJ2049 不容易系列之(4)——考新郎
2019-04-30
CodeForces 248B - Chilly Willy - 找规律
2019-04-30
POJ-2418 Hardwood Species(Trie树)(map)
2019-04-30
HDU-4300 Clairewd’s message + 4333(扩展KMP)
2019-04-30
HDU 1592 Half of and a Half(高精度)
2019-04-30
POJ-3304 Segments(计算几何)
2019-04-30
UVA-11538 Chess Queen(数学)
2019-04-30
UVA-11401 Triangle Counting(数学优化)
2019-04-30
Codeforces Round #369 (Div. 2)
2019-04-30
UVA 11426 GCD - Extreme (II)(欧拉函数)
2019-04-30
HDU-2838 Cow Sorting(树状数组)
2019-04-30
POJ-2299 Ultra-QuickSort(树状数组)(离散化)
2019-04-30
基于SSM的兼职论坛系统的设计与实现
2019-04-30
基于java的图书管理系统的设计与实现
2019-04-30
基于java的SSM框架理财管理系统的设计与实现
2019-04-30
基于java的ssm框架就业信息管理系统的设计
2019-04-30
基于java的ssm框架的旅游网站设计与实现
2019-04-30
基于java的SSM框架的流浪猫救助网站的设计与实现
2019-04-30