剑指Offer面试题：24.复杂链表的复制
一、题目：复杂链表的复制
题目：请实现函数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); }
正文到此结束
