题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解题思路
思路1：
先复制原始链表的结点
在元素链表的头结点开始找每个结点的random。每次都要从投开始找，然后连接起来，所以时间复杂度是o（n*n）
思路2：
用空间换时间。创建一个map映射表。<N,N1>(原始结点，复制的结点)。找到结点的random时间复杂度是o（1）。所以最后是o（n）。
思路3：
不使用辅助空间的情况下
image.png
代码实现
/*
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 cur = pHead;
//1.每个节点之后插入复制节点
while(cur != null) {
RandomListNode cloneNode = new RandomListNode(cur.label);
cloneNode.next = cur.next;
cur.next = cloneNode;
cur = cloneNode.next;
}
//2.复制节点插入 random 节点
cur = pHead;
while(cur != null) {
RandomListNode cloneNode = cur.next;
if(cur.random != null) {
cloneNode.random = cur.random.next;
}
cur = cloneNode.next;
}
//3.拆分
cur = pHead;
RandomListNode cloneHead = pHead.next;
while (cur.next != null) {
RandomListNode next = cur.next;
cur.next = next.next;
cur = next;
}
return cloneHead;
}
}
