新的链表的结构可以表示为：
~~~
static class NewNode {
private int val;
private NewNode next;
private NewNode rand;
public NewNode(int val) {
this.val = val;
this.next = null;
this.rand = null;
}
}
~~~
比如我们此时有这么一个链表：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-10 102525.png"/>
对应的初始化链表的方法：
~~~
/**
* 初始化链表
* @param nextArr 可以看作单链表的有序数组
* @param randPair 下标对，比如[[0, 2]]
* @return 链表NewNode
*/
public static NewNode createLinkedList(int[] nextArr, List<int[]> randPair){
if(nextArr == null || nextArr.length == 0) return null;
Map<Integer, NewNode> maps = new HashMap<>();
NewNode dummyNode = new NewNode(-1);
NewNode ptr = dummyNode;
int index = 0;
for (int val : nextArr) {
NewNode node = new NewNode(val);
maps.put(index, node);
ptr.next = node;
ptr = ptr.next;
index++;
}
ptr.next = null;
// 初始化rand对
for (int[] pair : randPair) {
maps.get(pair[0]).rand = maps.get(pair[1]);
}
return dummyNode.next;
}
~~~
那么，如果需要拷贝这个链表，我们可以使用`map`来进行辅助，比如下面的代码：
~~~
/**
* 链表拷贝，直接使用Map来存储老节点、新节点之间的对应关系即可。然后进行遍历映射
* @param list 待拷贝链表
* @return 新链表
*/
public NewNode copyLinkedList(NewNode list){
if(list == null) return list;
// 存储老节点 -> 新节点
Map<NewNode, NewNode> maps = new HashMap<>();
NewNode ptr = list;
while(ptr != null){
maps.put(ptr, new NewNode(ptr.val));
ptr = ptr.next;
}
ptr = list;
while(ptr != null){
maps.get(ptr).next = maps.get(ptr.next);
maps.get(ptr).rand = maps.get(ptr.rand);
ptr = ptr.next;
}
return maps.get(list);
}
~~~
如果要求空间复杂度为`O(1)`，也就是说除了元素节点之外，引入常数个空间。那么上面的方法就不适用。所以我们需要使用另一种方式。比如下图：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-10 104528.png"/>
也就是说我们只需要将节点成对进行保存对应链表信息，然后将绿色节点链抽离出来即可。对应代码：
~~~
/**
* 链表拷贝，将每个新节点链接到老节点的后面，然后再抽离
* @param list 待拷贝链表
* @return 新链表
*/
public NewNode copyLinkedList_2(NewNode list) {
if (list == null) return list;
NewNode ptr = list;
// 按照next信息，新建拷贝节点，并链接到原节点的后面
while(ptr != null){
NewNode qtr = ptr.next;
NewNode temp = new NewNode(ptr.val);
temp.next = ptr.next;
ptr.next = temp;
ptr = qtr;
}
// 成对遍历链表，然后保存对应的rand信息
ptr = list;
while(ptr != null){
if(ptr.rand != null) {
ptr.next.rand = ptr.rand.next;
}
ptr = ptr.next.next;
}
// 抽离新、旧链表
ptr = list;
NewNode dummyNode = new NewNode(-1);
NewNode qtr = dummyNode;
while(ptr != null){
qtr.next = ptr.next;
ptr.next = ptr.next.next;
ptr = ptr.next;
qtr = qtr.next;
}
return dummyNode.next;
}
~~~
不妨构建一个打印链表的函数：
~~~
/**
* 打印链表
* @param head
*/
public static void printLinkedList(NewNode head){
NewNode ptr = head;
while(ptr != null){
System.out.print(ptr.val);
if(ptr.rand != null){
System.out.print("[rand:"+ptr.rand.val+"]\t");
} else{
System.out.print("\t");
}
ptr = ptr.next;
}
System.out.println();
}
~~~
测试：
~~~
public static void main(String[] args) {
List<int[]> pairs = new ArrayList<>();
pairs.add(new int[]{0, 2}); // 1, 4
pairs.add(new int[]{2, 3}); // 4, 3
NewNode node = NewNode.createLinkedList(new int[]{1, 5, 4, 3, 2}, pairs);
System.out.println("原链表：");
NewNode.printLinkedList(node);
NewNode newNode = new CopyLinkedList().copyLinkedList_2(node);
System.out.println("拷贝链表：");
NewNode.printLinkedList(newNode);
}
~~~
结果：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-10 110317.png"/>
