复制带随机指针的链表
复制带随机指针的链表
作者：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:复制带随机指针的链表
