劍指Offer面試題：24.復雜鏈表的復制
題目：請實現函數ComplexListNode Clone(ComplexListNode head)，復制一個復雜鏈表。在復雜鏈表中，每個結點除了有一個Next指針指向下一個結點外，還有一個Sibling指向鏈表中的任意結點或者NULL。下圖是一個含有5個結點的復雜鏈表。圖中實線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。為簡單起見，指向NULL的指針沒有畫出。
一、題目：復雜鏈表的復制
題目：請實現函數ComplexListNode Clone(ComplexListNode head)，復制一個復雜鏈表。在復雜鏈表中，每個結點除了有一個Next指針指向下一個結點外，還有一個Sibling指向鏈表中的任意結點或者NULL。
結點的定義如下，采用C#語言描述：
public class ComplexListNode { public int Data { get; set; } public ComplexListNode Next { get; set; } public ComplexListNode Sibling { get; set; } public ComplexListNode(int data) { this.Data = data; } public ComplexListNode(int data, ComplexListNode next, ComplexListNode sibling = null) { this.Data = data; this.Next = next; this.Sibling = sibling; } }
下圖是一個含有5個結點的復雜鏈表。圖中實線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。為簡單起見，指向NULL的指針沒有畫出。
二、解題思路
2.1 O(n2)的普通解法
第一步是復制原始鏈表上的每一個結點，并用Next節點鏈接起來；
第二步是設置每個結點的Sibling節點指針。
對于一個含有n個結點的鏈表，由于定位每個結點的Sibling都需要從鏈表頭結點開始經過O(n)步才能找到，因此這種方法的總時間復雜度是O(n2)。
2.2 借助輔助空間的O(n)解法
第一步仍然是復制原始鏈表上的每個結點N創建N'，然后把這些創建出來的結點用Next鏈接起來。同時我們把<N,N'>的配對信息放到一個哈希表中。
第二步還是設置復制鏈表上每個結點的m_pSibling。由于有了哈希表，我們可以用O(1)的時間根據S找到S'。
此方法使用空間換時間。對于有n個結點的鏈表我們需要一個大小為O(n)的哈希表，也就是說我們以O(n)的空間消耗把時間復雜度由O(n2)降低到O(n)。
2.3 不借助輔助空間的O(n)解法
第一步仍然是根據原始鏈表的每個結點N創建對應的N'。（把N'鏈接在N的后面）
private static void CloneNodes(ComplexListNode head) { ComplexListNode node = head; while (node != null) { ComplexListNode cloned = new ComplexListNode(); cloned.Data = node.Data; cloned.Next = node.Next; cloned.Sibling = null; node.Next = cloned; node = cloned.Next; } }
第二步設置復制出來的結點的Sibling。（把N'的Sibling指向N的Sibling）
private static void ConnectSiblingNodes(ComplexListNode head) { ComplexListNode node = head; while (node != null) { ComplexListNode cloned = node.Next; if (node.Sibling != null) { cloned.Sibling = node.Sibling; } node = cloned.Next; } }
第三步把這個長鏈表拆分成兩個鏈表：把奇數位置的結點用Next鏈接起來就是原始鏈表，偶數數值的則是復制鏈表。
private static ComplexListNode ReconnectNodes(ComplexListNode head) { ComplexListNode node = head; ComplexListNode clonedHead = null; ComplexListNode clonedNode = null; if (node != null) { clonedHead = clonedNode = node.Next; node.Next = clonedNode.Next; node = node.Next; } while (node != null) { // 復制鏈表的連接 clonedNode.Next = node.Next; clonedNode = clonedNode.Next; // 原始鏈表的連接 node.Next = clonedNode.Next; node = node.Next; } return clonedHead; }
最后，將三個步驟銜接起來形成Clone方法：
public static ComplexListNode Clone(ComplexListNode head) { CloneNodes(head); ConnectSiblingNodes(head); return ReconnectNodes(head); }
三、單元測試
輔助方法的封裝
public static void TestPortal(string testName, ComplexListNode head) { if (!string.IsNullOrEmpty(testName)) { Console.WriteLine("{0} begins:", testName); } Console.WriteLine("The original list is:"); PrintList(head); ComplexListNode clonedHead = Clone(head); Console.WriteLine("The cloned list is:"); PrintList(clonedHead); } private static void PrintList(ComplexListNode head) { ComplexListNode node = head; while (node != null) { Console.WriteLine("The value of this node is: {0}.", node.Data); if (node.Sibling != null) { Console.WriteLine("The value of its sibling is: {0}.", node.Sibling.Data); } else { Console.WriteLine("This node does not have a sibling."); } Console.WriteLine(); node = node.Next; } } private static void BuildNodes(ComplexListNode node, ComplexListNode next, ComplexListNode sibling) { if (node != null) { node.Next = next; node.Sibling = sibling; } }
（1）Test1
// ----------------- // \|/ | // 1-------2-------3-------4-------5 // | | /|\ /|\ // --------+-------- | // ------------------------- public static void Test1() { ComplexListNode node1 = new ComplexListNode(1); ComplexListNode node2 = new ComplexListNode(2); ComplexListNode node3 = new ComplexListNode(3); ComplexListNode node4 = new ComplexListNode(4); ComplexListNode node5 = new ComplexListNode(5); BuildNodes(node1, node2, node3); BuildNodes(node2, node3, node5); BuildNodes(node3, node4, null); BuildNodes(node4, node5, node2); TestPortal("Test1", node1); }
（2）Test2
// Sibling指向結點自身 // ----------------- // \|/ | // 1-------2-------3-------4-------5 // | | /|\ /|\ // | | -- | // |------------------------| public static void Test2() { ComplexListNode node1 = new ComplexListNode(1); ComplexListNode node2 = new ComplexListNode(2); ComplexListNode node3 = new ComplexListNode(3); ComplexListNode node4 = new ComplexListNode(4); ComplexListNode node5 = new ComplexListNode(5); BuildNodes(node1, node2, null); BuildNodes(node2, node3, node5); BuildNodes(node3, node4, node3); BuildNodes(node4, node5, node2); TestPortal("Test2", node1); }
（3）Test3
// Sibling形成環 // ----------------- // \|/ | // 1-------2-------3-------4-------5 // | /|\ // | | // |---------------| public static void Test3() { ComplexListNode node1 = new ComplexListNode(1); ComplexListNode node2 = new ComplexListNode(2); ComplexListNode node3 = new ComplexListNode(3); ComplexListNode node4 = new ComplexListNode(4); ComplexListNode node5 = new ComplexListNode(5); BuildNodes(node1, node2, null); BuildNodes(node2, node3, node4); BuildNodes(node3, node4, null); BuildNodes(node4, node5, node2); TestPortal("Test3", node1); }
（4）Test4
// 只有一個結點 public static void Test4() { ComplexListNode node1 = new ComplexListNode(1); node1.Sibling = node1; TestPortal("Test4", node1); }
（5）Test5
// 魯棒性測試 public static void Test5() { TestPortal("Test5", null); }
浙公網安備 33010602011771號