新的鏈表的結構可以表示為：
~~~
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"/>
