复制带随机指针的链表
作者：Grey
原文地址：
题目描述
一种特殊的单链表节点类描述如下
class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } random 指针是单链表节点结构中新增的指针，random 可能指向链表中的任意一个节点，也可能指向 null，
给定一个由 Node 节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，返回复制的新链表的头节点。
注：要求时间复杂度O(N)，额外空间复杂度O(1)
OJ见：LeetCode 138. Copy List with Random Pointer
主要思路
假设原始链表如下，其中虚线表示 random 指针
由于空间复杂度需要O(1)，所以使用辅助数组的方式不可取，只能在链表上进行原地调整。
第一步，将当前节点的复制节点连在当前节点的下一个位置上，如上链表，a'为a的复制节点，其他节点同理，首先会得到如下链表
第二步，复制节点的 random 指针指向当前节点的 random 指针的下一个位置，以a节点为例，a节点的next就是a的复制节点a'，a节点的random节点的next就是a'的random指针
即a.next.random = a.random.next,由于random指针可能为空，所以a.next.random = a.random == null?null:a.random.next，其余节点类似，示例图如下
第三步，以上已经完成了链表元素的复制，接下来是分离原链表和复制链表。
以a和a'节点为例，分离的过程就是
a.next = a.next.next; a'.next = a'.next.next; 特别要注意最后一个节点，因为最后一个节点的next为空，所以，针对最后一个节点d和d'来说
d.next = null; d'.next = null; 最后返回复制链表的头部即可，本例中，返回a'节点即可。
完整代码见
class Solution { public static Node copyRandomList(Node head) { if (head == null) { return null; } // 以下方法将每个节点的复制节点都在这个节点后面 // 如果链表是:1->2->3->4 复制以后，会变成： 1->1->2->2->3->3->4->4 Node cur = head; while (cur != null) { Node tmp = cur.next; Node copy = new Node(cur.val); cur.next = copy; copy.next = tmp; cur = tmp; } // 以下方法是设置每个复制节点的random指针 cur = head; while (cur != null) { cur.next.random = cur.random == null ? null : cur.random.next; // 无须判断cur.next是否空指针，因为cur永远是原链表的位置，cur只要不为null // cur.next必为复制节点，所以cur只要不为空，cur.next一定存在 cur = cur.next.next; } // 以下方法是断开原链表和复制链表,注意最后一个节点 cur = head; Node copyHead = head.next; Node copyCur = copyHead; Node start = copyHead.next; head.next = null; int i = 1; while (start != null) { Node next = start.next; if ((i & 1) == 1) { cur.next = start; cur = start; } else { copyCur.next = start; copyCur = start; } i++; start = next; } cur.next = null; copyCur.next = null; return copyHead; } } 本题的所有图例见: processon:复制带随机指针的链表
