题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
题目分析
这道题有三种解法。
解法一
就是普通的解法，先复制节点，用p.next连接起来。然后再去设置p.random指针指向，不过这个设置又需要从头节点开始查。
所以总的时间复杂度为O（n2）
解法二
用map来保存<N，N`>，这样就很容易设置p.random了，比如我们在节点S处和节点S`处，我们通过S可以得到N，那么<N，N`>对应，
我们就可以就可以使得S`的next指向N`了。这是通过空间换时间
解法三
第三种就是比较复杂些，但是不用空间换时间也能达到O（n）
- 第一步，对链表的每个节点N创建N‘，并链接在N的后面。
- 设置复制出来的p.random。节点N指向S，那么N'指向S'，而N和N'相邻，那么S和S'也相邻。
- 把长链表拆开成两个链表。
代码
这里只给出第二种和第三种的参考代码。
解法二：
// 第一种
function RandomListNode(x) {
this.label = x;
this.next = null;
this.random = null;
}
function Clone(pHead) {
// write code here
if (pHead === null) {
return null;
}
const map = new Map();
let p, p2;
p = pHead;
p2 = new RandomListNode(pHead.label);
const pHead2 = p2;
map.set(p, p2);
while (p) {
if (p.next) p2.next = new RandomListNode(p.next.label);
else p2.next = null;
p = p.next;
p2 = p2.next;
map.set(p, p2);
}
p = pHead;
p2 = pHead2;
while (p !== null) {
p2.random = map.get(p.random);
p = p.next;
p2 = p2.next;
}
return pHead2;
}
解法三：
// 第二种
/* function RandomListNode(x){
this.label = x;
this.next = null;
this.random = null;
}*/
function Clone2(pHead) {
cloneNodes(pHead);
connectRandom(pHead);
return reconnectNodes(pHead);
}
function cloneNodes(pHead) {
// 复制链表
let pNode = pHead;
while (pNode !== null) {
const newNode = new RandomListNode(pNode.label);
newNode.next = pNode.next;
pNode.next = newNode;
pNode = newNode.next;
}
}
function connectRandom(pHead) {
// 设置random指针
let pNode = pHead;
while (pNode !== null) {
if (pNode.random !== null) {
pNode.next.random = pNode.random.next;
}
pNode = pNode.next.next;
}
}
function reconnectNodes(pHead) {
// 拆开链表
let pNode = pHead;
let newNodeHead = null,
newNode = null;
if (pNode !== null) {
newNodeHead = newNode = pNode.next;
pNode.next = newNode.next;
pNode = newNode.next;
}
while (pNode !== null) {
newNode.next = pNode.next;
newNode = newNode.next;
pNode.next = newNode.next;
pNode = pNode.next;
}
return newNodeHead;
}