本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖
面試題35：復(fù)雜鏈表的復(fù)制
題目要求：在復(fù)雜鏈表中解藻，每個(gè)節(jié)點(diǎn)除了有一個(gè)next指針指向下一個(gè)節(jié)點(diǎn)老充，還有一個(gè)random指針指向鏈表中的任意節(jié)點(diǎn)或null，請(qǐng)完成一個(gè)能夠復(fù)制復(fù)雜鏈表的函數(shù)螟左。
解題思路：
此題定義了一種新的數(shù)據(jù)結(jié)構(gòu)蚂维，復(fù)雜鏈表。與傳統(tǒng)鏈表的區(qū)別是多了一個(gè)random指針路狮。本題的關(guān)鍵點(diǎn)也就在如何高效地完成random指針的復(fù)制。
| 解法 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|---|
| 解法一 | o(n^2) | o(1) |
| 解法二 | o(n) | o(n) |
| 解法三 | o(n) | o(1) |
解法一比較直接：
先把這個(gè)復(fù)雜鏈表當(dāng)做傳統(tǒng)鏈表對(duì)待蔚约，只復(fù)制val域與next域（時(shí)間o(n)）奄妨，再?gòu)男骆湵淼念^部開(kāi)始，對(duì)random域賦值（時(shí)間o(n^2)）苹祟。
package chapter4;
import java.util.HashMap;
/**
* Created by ryder on 2017/7/18.
* 復(fù)制復(fù)雜鏈表
*/
public class P187_CopyComplexList {
public static class ComplexListNode{
int val;
ComplexListNode next;
ComplexListNode random;
public ComplexListNode(int val) {
this.val = val;
}
@Override
public String toString() {
StringBuilder ret = new StringBuilder();
ComplexListNode cur = this;
while(cur!=null) {
ret.append(cur.val);
if(cur.random!=null)
ret.append("("+cur.random.val+")");
else{
ret.append("(_)");
}
ret.append('\t');
cur = cur.next;
}
return ret.toString();
}
}
//解法一
//time:o(n^2) space:o(1) 新鏈表使用的n個(gè)長(zhǎng)度的空間不算入
//先復(fù)制val與next（時(shí)間o(n)）砸抛，再?gòu)?fù)制random域（時(shí)間o(n^2)）
public static ComplexListNode clone1(ComplexListNode head){
if(head==null)
return null;
ComplexListNode newHead = new ComplexListNode(head.val);
ComplexListNode cur = head.next;
ComplexListNode newCur = null;
ComplexListNode newCurPrev = newHead;
while (cur!=null){
newCur = new ComplexListNode(cur.val);
newCurPrev.next = newCur;
newCurPrev = newCurPrev.next;
cur = cur.next;
}
cur = head;
newCur = newHead;
ComplexListNode temp = head;
ComplexListNode newTemp = newHead;
while(cur!=null){
if(cur.random!=null){
temp = head;
newTemp = newHead;
while (temp!=cur.random){
temp = temp.next;
newTemp = newTemp.next;
}
newCur.random = newTemp;
}
cur = cur.next;
newCur = newCur.next;
}
return newHead;
}
public static void main(String[] args){
ComplexListNode head = new ComplexListNode(1);
ComplexListNode c2 = new ComplexListNode(2);
ComplexListNode c3 = new ComplexListNode(3);
ComplexListNode c4 = new ComplexListNode(4);
ComplexListNode c5 = new ComplexListNode(5);
head.next = c2;
head.random = c3;
head.next.next = c3;
head.next.random = c5;
head.next.next.next = c4;
head.next.next.next.next = c5;
head.next.next.next.random = c2;
System.out.println("original:"+'\t'+head);
System.out.println("clone1: "+'\t'+clone1(head));
System.out.println("clone2: "+'\t'+clone2(head));
System.out.println("clone3: "+'\t'+clone3(head));
}
}
解法二是用空間換時(shí)間:
解法一時(shí)間復(fù)雜度高的原因在于確定random域的費(fèi)時(shí)，即假設(shè)原鏈表第m個(gè)節(jié)點(diǎn)指向第k個(gè)節(jié)點(diǎn)树枫，而在新鏈表的第m個(gè)節(jié)點(diǎn)處無(wú)法直接得到第k個(gè)節(jié)點(diǎn)直焙，需從頭遍歷。很自然的想法是用一個(gè)哈希表記錄舊鏈表每個(gè)節(jié)點(diǎn)到新鏈表對(duì)應(yīng)節(jié)點(diǎn)的映射砂轻，從而可以將時(shí)間復(fù)雜度降低為o(n)奔誓。
//解法二
//time:o(n) space:o(n)
//使用o(n)的空間，換取了時(shí)間復(fù)雜度的降低
public static ComplexListNode clone2(ComplexListNode head) {
if(head==null)
return null;
HashMap<ComplexListNode,ComplexListNode> oldToNew = new HashMap<>();
ComplexListNode newHead = new ComplexListNode(head.val);
oldToNew.put(head,newHead);
ComplexListNode cur = head.next;
ComplexListNode newCur = null;
ComplexListNode newCurPrev = newHead;
while (cur!=null){
newCur = new ComplexListNode(cur.val);
oldToNew.put(cur,newCur);
newCurPrev.next = newCur;
newCurPrev = newCurPrev.next;
cur = cur.next;
}
cur = head;
newCur = newHead;
while(cur!=null){
if(cur.random!=null){
newCur.random = oldToNew.get(cur.random);
}
cur = cur.next;
newCur = newCur.next;
}
return newHead;
}
解法三：
思路很巧妙搔涝。將復(fù)制的任務(wù)分為如下三個(gè)部分：
1）cloneNodes完成新鏈表節(jié)點(diǎn)的創(chuàng)建厨喂，僅對(duì)val域賦值，且每個(gè)新節(jié)點(diǎn)接在原鏈表對(duì)應(yīng)節(jié)點(diǎn)的后面庄呈。如A->B->C,處理完后為A->A'->B->B'->C->C'蜕煌，時(shí)間復(fù)雜度o(n)。
2）connectRandomNode完成random域的賦值诬留。假設(shè)A.random=C,我們需要設(shè)置A'.random=C'斜纪，此處獲取C'可以在o(1)的時(shí)間復(fù)雜度完成贫母，全部賦值完畢時(shí)間復(fù)雜度為o(n)。
3）reconnectNodes就是將上述鏈表重組盒刚，使A->A'->B->B'->C->C'變?yōu)锳->B->C腺劣，A'->B'->C'。此處需要注意尾部null的處理伪冰。
//解法三
//time:o(n) space:o(1)
public static ComplexListNode clone3(ComplexListNode head) {
if(head==null)
return null;
cloneNodes(head);
connectRandomNodes(head);
return reconnectNodes(head);
}
public static void cloneNodes(ComplexListNode head){
ComplexListNode cur = head;
ComplexListNode temp = null;
while (cur!=null){
temp = new ComplexListNode(cur.val);
temp.next = cur.next;
cur.next = temp;
cur = cur.next.next;
}
}
public static void connectRandomNodes(ComplexListNode head){
ComplexListNode cur = head;
ComplexListNode curNext = head.next;
while (true){
if(cur.random!=null)
curNext.random = cur.random.next;
cur = cur.next.next;
if(cur == null)
break;
curNext = curNext.next.next;
}
}
public static ComplexListNode reconnectNodes(ComplexListNode head){
ComplexListNode newHead = head.next;
ComplexListNode cur = head;
ComplexListNode newCur = newHead;
while (true){
cur.next = cur.next.next;
cur = cur.next;
if(cur==null){
newCur.next = null;
break;
}
newCur.next = newCur.next.next;
newCur = newCur.next;
}
return newHead;
}
運(yùn)行結(jié)果
original: 1(3) 2(5) 3(_) 4(2) 5(_)
clone1: 1(3) 2(5) 3(_) 4(2) 5(_)
clone2: 1(3) 2(5) 3(_) 4(2) 5(_)
clone3: 1(3) 2(5) 3(_) 4(2) 5(_)
