面試 18：復(fù)雜鏈表的復(fù)制（劍指 Offer 第 26 題）
在上一篇推文中丈攒，我們留下的習(xí)題是來(lái)自《劍指 Offer》 的面試題 26：復(fù)雜鏈表的復(fù)制镣陕。
請(qǐng)實(shí)現(xiàn)復(fù)雜鏈表的復(fù)制坝撑，在復(fù)雜鏈表中厉碟，每個(gè)結(jié)點(diǎn)除了 next 指針指向下一個(gè)結(jié)點(diǎn)外查库，還有一個(gè) sibling 指向鏈表中的任意結(jié)點(diǎn)或者 NULL碍庵。比如下圖就是一個(gè)含有 5 個(gè)結(jié)點(diǎn)的復(fù)雜鏈表映企。
提前想好測(cè)試用例
依舊是我們熟悉的第一步，先想好我們的測(cè)試用例：
- 輸入一個(gè) null 静浴，期望什么也不輸出堰氓；
- 輸入一個(gè)結(jié)點(diǎn)，sibling 指向自身苹享，期望打印符合題干的值双絮；
- 輸入多個(gè)結(jié)點(diǎn)浴麻，部分 sibling 指向 null，期望打印符合題干的值囤攀。
思考程序邏輯
測(cè)試用例思考完畢软免，自然是開(kāi)始思考我們的測(cè)試邏輯了，在思考的過(guò)程中焚挠，我們不妨嘗試和面試官進(jìn)行溝通膏萧，這樣可以避免我們走不少?gòu)澛罚乙踩菀捉o面試官留下一個(gè)善于思考和溝通的好印象蝌衔。
極易想到的邏輯是榛泛，我們先復(fù)制我們傳統(tǒng)的單鏈表，然后再遍歷單鏈表噩斟，復(fù)制 sibling 的指向曹锨。
假設(shè)鏈表中有個(gè)結(jié)點(diǎn) A，A 的 sibling 指向結(jié)點(diǎn) B剃允，這個(gè) B 可能在 A 前面也可能在 A 后面沛简，所以我們唯一的辦法只有從頭結(jié)點(diǎn)開(kāi)始遍歷。對(duì)于一個(gè)含有 n 個(gè)結(jié)點(diǎn)的鏈表斥废，由于定位每個(gè)結(jié)點(diǎn)的 sibling 都需要從鏈表頭結(jié)點(diǎn)開(kāi)始經(jīng)過(guò) O(n) 步才能找到椒楣，因此這種方法的時(shí)間復(fù)雜度是 O(n2)。
當(dāng)我們告知面試官我們這樣的思路的時(shí)候牡肉，面試官告訴我們撒顿，他期待的并不是這樣的算法，這樣的算法時(shí)間復(fù)雜度也太高了荚板，希望能有更加簡(jiǎn)單的方式。
得到了面試官的訴求吩屹，我們?cè)賮?lái)看看我們前面的想法時(shí)間都花在哪兒去了跪另。
很明顯，我們上面的想法在定位 sibling 指向上面花了大量的時(shí)間煤搜，我們可以嘗試在這上面進(jìn)行優(yōu)化免绿。我們還是分為兩步：第一步仍然是先復(fù)制原始鏈表上的每個(gè)結(jié)點(diǎn) N 創(chuàng)建 N1，然后把這些創(chuàng)建出來(lái)的結(jié)點(diǎn)用 next 連接起來(lái)擦盾。同時(shí)我們把 <N,N1> 的配對(duì)信息放在一個(gè)哈希表中嘲驾。第二步是設(shè)置復(fù)制鏈表的 sibling 指向，如果原始鏈表中有 N 指向 S迹卢，那么我們的復(fù)制鏈表中必然存在 N1 指向 S1 辽故。由于有了哈希表，我們可以用 O(1) 的時(shí)間腐碱，根據(jù) S 找到 S1誊垢。
這樣的方法降低了時(shí)間成本，我們高興地與面試官分享我們的想法，卻被面試官指出喂走，這樣的想法雖然把時(shí)間復(fù)雜度降低到了 O(n)殃饿，但卻由于哈希表的存在，需要 O(n) 的空間芋肠，而他所期望的方法是不占用任何輔助空間的乎芳。
接下來(lái)我們?cè)贀Q一下思路，不用輔助空間帖池，我們卻要用更少的實(shí)際解決 sibling 的指向問(wèn)題奈惑。
我們前面似乎對(duì)于指向都采用過(guò)兩個(gè)指針的方法，這里似乎可以用類似的處理方式處理碘裕。
我們不妨利用原有鏈表對(duì)每個(gè)結(jié)點(diǎn) N 在后面直接在后面創(chuàng)建 N1携取，這樣相當(dāng)于我們擴(kuò)長(zhǎng)原始鏈表長(zhǎng)度為現(xiàn)有鏈表的 2 倍，奇數(shù)位置的結(jié)點(diǎn)連接起來(lái)是原始鏈表帮孔，偶數(shù)位置的結(jié)點(diǎn)連接起來(lái)就是我們的復(fù)制鏈表雷滋。
開(kāi)始編寫代碼
我們先完成第一部分的代碼。根據(jù)原始鏈表的每個(gè)結(jié)點(diǎn) N 文兢，創(chuàng)建 N1晤斩，并把 N 的 next 指向 N1，N1 的 next 指向 N 的 next姆坚。
private static void cloneNodes(Node head) {
Node node = null;
while (head != null) {
// 先新建結(jié)點(diǎn)
node = new Node(head.data);
// 再把head 的 next 指向 node 的 next
node.next = head.next;
// 然后把 node 作為 head 的 next
head.next = node;
// 最后遍歷條件
head = node.next;
}
}
上面完成了復(fù)制結(jié)點(diǎn)澳泵，下面我們需要編寫 sibling 的指向復(fù)制。
我們的思想是：當(dāng) N 執(zhí)行 S兼呵，那么 N1 就應(yīng)該指向 S1兔辅，即 N.next.sibling = N.sibling.next；
private static void connectNodes(Node head) {
while (head != null) {
if (head.sibling != null) {
//如果 當(dāng)前結(jié)點(diǎn)的 sibling 不為 null,那就把它后面的復(fù)制結(jié)點(diǎn)指向當(dāng)前sibling指向的下一個(gè)結(jié)點(diǎn)
head.next.sibling = head.sibling.next;
}
// 遍歷
head = head.next.next;
}
}
最后我們只需要拿出原本的鏈表（奇數(shù)）和復(fù)制的鏈表（偶數(shù)）即可击喂。
private static Node reconnectList(Node head) {
if (head == null)
return null;
// 用于存放復(fù)制鏈表的頭結(jié)點(diǎn)
Node cloneHead = head.next;
// 用于記錄當(dāng)前處理的結(jié)點(diǎn)
Node temp = cloneHead;
// head 的 next 還是要指向原本的 head.next
// 實(shí)際上現(xiàn)在由于復(fù)制后维苔，應(yīng)該是 head.next.next，即cloneHead.next
head.next = cloneHead.next;
// 指向新的被復(fù)制結(jié)點(diǎn)
head = head.next;
while (head != null) {
// temp 代表的是復(fù)制結(jié)點(diǎn)
// 先進(jìn)行賦值
temp.next = head.next;
// 賦值結(jié)束應(yīng)該給 next 指向的結(jié)點(diǎn)賦值
temp = temp.next;
// head 的下一個(gè)結(jié)點(diǎn)應(yīng)該指向被賦值的下一個(gè)結(jié)點(diǎn)
head.next = temp.next;
head = temp.next;
}
return cloneHead;
}
合并后的最終代碼就是：
public class Test18 {
private static class Node {
int data;
Node next;
Node sibling;
Node(int data) {
this.data = data;
}
}
private static Node complexListNode(Node head) {
if (head == null)
return null;
// 第一步懂昂，復(fù)制結(jié)點(diǎn)介时，并用 next 連接
cloneNodes(head);
// 第二步，把 sibling 也復(fù)制起來(lái)
connectNodes(head);
// 第三步凌彬，返回偶數(shù)結(jié)點(diǎn)沸柔，連接起來(lái)就是復(fù)制的鏈表
return reconnectList(head);
}
private static void cloneNodes(Node head) {
Node node = null;
while (head != null) {
// 先新建結(jié)點(diǎn)
node = new Node(head.data);
// 再把head 的 next 指向 node 的 next
node.next = head.next;
// 然后把 node 作為 head 的 next
head.next = node;
// 最后遍歷條件
head = node.next;
}
}
private static void connectNodes(Node head) {
while (head != null) {
if (head.sibling != null) {
// 如果 當(dāng)前結(jié)點(diǎn)的 sibling 不為 null,那就把它后面的復(fù)制結(jié)點(diǎn)指向當(dāng)前sibling指向的下一個(gè)結(jié)點(diǎn)
head.next.sibling = head.sibling.next;
}
// 遍歷
head = head.next.next;
}
}
private static Node reconnectList(Node head) {
if (head == null)
return null;
// 用于存放復(fù)制鏈表的頭結(jié)點(diǎn)
Node cloneHead = head.next;
// 用于記錄當(dāng)前處理的結(jié)點(diǎn)
Node cloneNode = cloneHead;
// head 的 next 還是要指向原本的 head.next
// 實(shí)際上現(xiàn)在由于復(fù)制后，應(yīng)該是 head.next.next铲敛，即cloneHead.next
head.next = cloneHead.next;
// 因?yàn)槲覀兊谝粋€(gè)結(jié)點(diǎn)已經(jīng)拆分了褐澎，所以需要指向新的被復(fù)制結(jié)點(diǎn)才可以開(kāi)始循環(huán)
head = head.next;
while (head != null) {
// cloneNode 代表的是復(fù)制結(jié)點(diǎn)
// 先進(jìn)行賦值
cloneNode.next = head.next;
// 賦值結(jié)束應(yīng)該給 next 指向的結(jié)點(diǎn)賦值
cloneNode = cloneNode.next;
// head 的下一個(gè)結(jié)點(diǎn)應(yīng)該指向被賦值的下一個(gè)結(jié)點(diǎn)
head.next = cloneNode.next;
head = cloneNode.next;
}
return cloneHead;
}
public static void main(String[] args) {
Node head1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
head1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
head1.sibling = node4;
node2.sibling = null;
node3.sibling = node5;
node4.sibling = node2;
node5.sibling = head1;
print(head1);
Node root = complexListNode(head1);
System.out.println();
print(head1);
print(root);
System.out.println();
System.out.println(isSameLink(head1, root));
}
private static boolean isSameLink(Node head, Node root) {
while (head != null && root != null) {
if (head == root) {
head = head.next;
root = root.next;
} else {
return false;
}
}
return head == null && root == null;
}
private static void print(Node head) {
Node temp = head;
while (head != null) {
System.out.print(head.data + "->");
head = head.next;
}
System.out.println("null");
while (temp != null) {
System.out.println(temp.data + "=>" + (temp.sibling == null ? "null" : temp.sibling.data));
temp = temp.next;
}
}
}
驗(yàn)證測(cè)試用例
寫畢代碼，我們驗(yàn)證我們的測(cè)試用例伐蒋。
- 輸入一個(gè) null 乱凿，也不會(huì)輸出顽素，測(cè)試通過(guò)；
- 輸入一個(gè)結(jié)點(diǎn)徒蟆，sibling 指向自身胁出，測(cè)試通過(guò)；
- 輸入多個(gè)結(jié)點(diǎn)段审，部分 sibling 指向 null全蝶，測(cè)試通過(guò)。
課后習(xí)題
下一次推文的習(xí)題來(lái)自于《劍指 Offer》第 29 題：數(shù)組中超過(guò)一半的數(shù)字
面試題：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半寺枉，請(qǐng)找出這個(gè)數(shù)字并輸出抑淫。比如 {1,2,3,2,2,2,1} 中 2 的次數(shù)是 4，數(shù)組長(zhǎng)度為 7姥闪，所以輸出 2始苇。要求不能修改輸入的數(shù)組。
