复杂链表的复制
题目
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
思路
开始我个人想法是直接新建一个链表，然后新建所有的节点，再给所有新节点设计next和random指向，完成一个复杂链表的复制。
但是,当我自己实现起来的时候发现太复杂了，有点难…
好在有讨论区，看了看各位大神的解法，个人觉得以拼接+分割的方式比较简单
过程
首先，如下图我们创建一个复杂链表
（这里为了方便画图，就只给一个节点设置了random）
在原有链表上复制节点本身，生成一个新的链表，像下图这样
我用黄色标记的节点就是新建立的节点。然后我们在给新节点设计好random指向就完成了拼接操作
（以下为设计random指向的代码）
//head 为复制后的链表
cur = head;
//遍历链表，设计新节点的random（要注意的是新节点的random指向也应该为新节点）
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
//cur用于指向原来的节点，cur.next为新节点
//所以新节点random（cur.next.random）指向的为原节点random的新节点（cur.random.next）
}
cur = cur.next.next;
}
最后，我们再进行分割就大功告成啦！
cur = head.next;
Node pre = head;
Node res = head.next;
// pre代表原来的链表 res代表复制的链表
while (cur.next != null) {
pre.next = pre.next.next;
cur.next = cur.next.next;
pre = pre.next;
cur = cur.next;
}
最重要的还是要有思路，思路有了，代码自然也就迎刃而解了。
完整实现代码
/**
* 题目：
* 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，
* 每个节点除了有一个 next 指针指向下一个节点，
* 还有一个 random 指针指向链表中的任意节点或者 null。
* <p>
* 思路：
* 拼接+分割
*/
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
public Node copy(Node head) {
if (head == null) {
return null;
}
Node cur = head;
//在原有节点上复制各个节点
while (cur != null) {
Node tmp = new Node(cur.val);
tmp.next = cur.next;
cur.next = tmp;
cur = tmp.next;
}
//构建复制的那一份节点的random
cur = head;
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
//现在只需要将链表拆分为两份就可以了
cur = head.next;
Node pre = head;
Node res = head.next;
// pre代表原来的链表 res代表复制的链表
while (cur.next != null) {
pre.next = pre.next.next;
cur.next = cur.next.next;
pre = pre.next;
cur = cur.next;
}
pre.next = null;//最后一元素的next被复制的链表给占了，手动补全
return res;
}