【面试题26】复杂链表的复制

【题目描述】

请实现函数ComplexListNode* Clone(ComplexListNode* pHead)。

复制一个复杂链表，每个结点，除了有一个m_pNext指针指向下一个结点，还有一个m_pSibling指向链表中的任意结点或者null。

【解决方案】

方法二：

我的代码实现，仅供参考：

 1         public static ComplexListNode Clone(ComplexListNode head)
 2         {
 3             CloneNode(head);
 4             ConnectSiblingNodes(head);
 5             return ReconnectNodes(head);
 6         }
 7 
 8         /// <summary>
 9         /// 复制原始链表
10         /// </summary>
11         /// <param name="head"></param>
12         public static void CloneNode(ComplexListNode head)
13         {
14             ComplexListNode node = head;
15 
16             while (node != null)
17             {
18                 ComplexListNode cloneNode = new ComplexListNode();
19 
20                 cloneNode.Value = node.Value;
21                 cloneNode.Next = node.Next;
22 
23                 node.Next = cloneNode;
24                 node = cloneNode.Next;
25             }
26         }
27 
28         /// <summary>
29         /// 设置Sibling
30         /// </summary>
31         /// <param name="head"></param>
32         public static void ConnectSiblingNodes(ComplexListNode head)
33         {
34             ComplexListNode node = head;
35 
36             while (node != null)
37             {
38                 ComplexListNode cloneNode = node.Next;
39 
40                 if (node.Sibling != null)
41                 {
42                     cloneNode.Sibling = node.Sibling.Next;
43                 }
44 
45                 node = cloneNode.Next;
46             }
47         }
48 
49         /// <summary>
50         /// 将CloneNode复制出来
51         /// </summary>
52         /// <param name="head"></param>
53         /// <returns></returns>
54         public static ComplexListNode ReconnectNodes(ComplexListNode head)
55         {
56             ComplexListNode node = head;
57             ComplexListNode cloneHead = null;
58             ComplexListNode cloneNode = null;
59 
60             if (node != null)
61             {
62                 cloneHead = cloneNode = node.Next;
63                 node.Next = cloneNode.Next;
64                 node = node.Next;
65             }
66 
67             while (node != null)
68             {
69                 cloneNode.Next = node.Next;
70                 cloneNode = cloneNode.Next;
71                 node.Next = cloneNode.Next;
72                 node = node.Next;
73             }
74 
75             return cloneHead;
76         }