题目
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
分析
(1),1 -> 2 -> 3
(2),1 -> 1(copy) -> 2 ->2(copy) -> 3 -> 3 (copy)
(3),设置每个复制节点的random节点
(4),分离出新的链表即可
代码实现
/*
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 pHead;
}
RandomListNode cur = pHead;
RandomListNode next = null;
while(cur != null){
RandomListNode tmp = new RandomListNode(cur.label);
next = cur.next;
cur.next = tmp;
tmp.next = next;
cur = next;
}
cur = pHead;
while(cur != null){
next = cur.next.next;
if(cur.random != null){
cur.next.random = cur.random.next;
}
cur = next;
}
RandomListNode res = pHead.next;
RandomListNode curRes = res;
cur = pHead;
while(cur != null){
cur.next = cur.next.next;
if(curRes.next != null){
curRes.next = curRes.next.next;
}
cur = cur.next;
curRes = curRes.next;
}
return res;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)