題目：
圖片.png
public static class Node {
public int value;
public Node next;
public Node rand;
public Node(int data) {
this.value = data;
}
}
分析：
新的鏈表也就是說要新開辟一塊內(nèi)存來構(gòu)建與原鏈表結(jié)構(gòu)和值相等的新鏈表，而不是僅僅new 一個(gè)Node指向原鏈表笋粟。
這道題目要求在時(shí)間復(fù)雜度O（n）的情況內(nèi)完成雇锡。而在構(gòu)建新節(jié)點(diǎn)的next和rand時(shí)如何快速獲得新節(jié)點(diǎn)與原節(jié)一一對應(yīng)的關(guān)系就是一大難點(diǎn)了摄闸。
解法一：使用HashMap結(jié)構(gòu)輔助
能使用輔助結(jié)構(gòu)時(shí)用這種方式，特點(diǎn)是簡單
在能使用額外數(shù)據(jù)結(jié)構(gòu)的情況下墨叛，對這道題來說用HashMap是很方便的闷畸。
因?yàn)橛肏ashMap<Node,Node>就能輕松將原鏈表節(jié)點(diǎn)與新鏈表節(jié)點(diǎn)的關(guān)系對應(yīng)起來尝盼。
public static Node copyListWithRand1(Node head) {
HashMap<Node, Node> map = new HashMap<Node, Node>();
Node cur = head;
//新節(jié)點(diǎn)復(fù)制原節(jié)點(diǎn)值，并與原節(jié)點(diǎn)一一對應(yīng)地放入HashMap中
while (cur != null) {
map.put(cur, new Node(cur.value));
cur = cur.next;
}
//新節(jié)點(diǎn)的next和rand一一對應(yīng)原節(jié)點(diǎn)的next和rand構(gòu)建
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).rand = map.get(cur.rand);
cur = cur.next;
}
return map.get(head);
}
解法二：不能用其他數(shù)據(jù)結(jié)構(gòu)的方法
將復(fù)制的新節(jié)點(diǎn)放在原節(jié)點(diǎn)后
例如原鏈表是：1==>3==>4==>6==>7
復(fù)制后的鏈表為：1==>1==>3==>3==>4==>4==>6==>6==>7==>7
這樣新節(jié)點(diǎn)與原節(jié)點(diǎn)一一對應(yīng)的關(guān)系就出來了：新節(jié)點(diǎn)就是原節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)即next
public static Node copyListWithRand2(Node head) {
if(head == null) {
return head;
}
Node curHead = head;
Node curCopy = null;
//在每個(gè)節(jié)點(diǎn)后面copy一個(gè)value相等的新節(jié)點(diǎn)
while(curHead != null) {
curCopy = new Node(curHead.value);
curCopy.next = curHead.next;
curHead.next = curCopy;
curHead = curCopy.next;
}
//copy相應(yīng)的rand指針
curHead = head;
while(curHead != null) {
curCopy = curHead.next;
if(curHead.rand != null) {
curCopy.rand = curHead.rand.next;
}else {
curCopy.rand = null;
}
curHead = curCopy.next;
}
//將copy鏈表分離出來
Node newHead = head.next;
curHead = head;
curCopy = curHead.next;
while(curHead != null) {
curHead.next = curCopy.next;
if(curCopy.next != null) {
curCopy.next = curCopy.next.next;
curCopy = curCopy.next;
}else {
curCopy.next = null;
}
curHead = curHead.next;
}
return newHead;
}
全代碼（含測試代碼）
public class CopyListWithRandom {
public static class Node {
public int value;
public Node next;
public Node rand;
public Node(int data) {
this.value = data;
}
}
public static Node copyListWithRand1(Node head) {
if(head == null) {
return head;
}
HashMap<Node, Node> map = new HashMap<>();
Node cur = head;
while(cur != null) {
map.put(cur, new Node(cur.value));
cur = cur.next;
}
cur = head;
while(cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).rand = map.get(cur.rand);
cur = cur.next;
}
return map.get(head);
}
public static Node copyListWithRand2(Node head) {
if(head == null) {
return head;
}
Node curHead = head;
Node curCopy = null;
//在每個(gè)節(jié)點(diǎn)后面copy一個(gè)value相等的新節(jié)點(diǎn)
while(curHead != null) {
curCopy = new Node(curHead.value);
curCopy.next = curHead.next;
curHead.next = curCopy;
curHead = curCopy.next;
}
//copy相應(yīng)的rand指針
curHead = head;
while(curHead != null) {
curCopy = curHead.next;
if(curHead.rand != null) {
curCopy.rand = curHead.rand.next;
}else {
curCopy.rand = null;
}
curHead = curCopy.next;
}
//將copy鏈表分離出來
Node newHead = head.next;
curHead = head;
curCopy = curHead.next;
while(curHead != null) {
curHead.next = curCopy.next;
if(curCopy.next != null) {
curCopy.next = curCopy.next.next;
curCopy = curCopy.next;
}else {
curCopy.next = null;
}
curHead = curHead.next;
}
return newHead;
}
public static void printRandLinkedList(Node head) {
Node cur = head;
System.out.print("order: ");
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.next;
}
System.out.println();
cur = head;
System.out.print("rand: ");
while (cur != null) {
System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
cur = cur.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = null;
Node res1 = null;
Node res2 = null;
printRandLinkedList(head);
res1 = copyListWithRand1(head);
printRandLinkedList(res1);
res2 = copyListWithRand2(head);
printRandLinkedList(res2);
printRandLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
head.next.next.next.next.next = new Node(6);
head.rand = head.next.next.next.next.next; // 1 -> 6
head.next.rand = head.next.next.next.next.next; // 2 -> 6
head.next.next.rand = head.next.next.next.next; // 3 -> 5
head.next.next.next.rand = head.next.next; // 4 -> 3
head.next.next.next.next.rand = null; // 5 -> null
head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4
printRandLinkedList(head);
res1 = copyListWithRand1(head);
printRandLinkedList(res1);
res2 = copyListWithRand2(head);
printRandLinkedList(res2);
printRandLinkedList(head);
System.out.println("=========================");
}
}
