復雜鏈表的復制，復雜鏈表復制

復雜鏈表的復制，復雜鏈表復制

題目：有一個復雜鏈表，其結點除了有一個m_pNext指針指向下一個結點外，還有一個m_pSibling指向鏈表中的任一結點或者NULL。其結點的C++定義如下：

 1 struct ComplexNode
 2 
 3 {
 4 
 5     int m_nValue;
 6 
 7     ComplexNode* m_pNext;
 8 
 9     ComplexNode* m_pSibling;
10 
11 };

請完成函數ComplexNode* Clone(ComplexNode* pHead)，以復制一個復雜鏈表。

思路:分三步，在不用輔助空間的情況下實現O(n)的時間效率。第一步，復制原始鏈表的任意結點N並創建新結點N‘，再把N’鏈接到N的後面

第二步，如果原始鏈表的結點N的m_pSibling指向S，則它對應的復制結點N‘的m_pSibling指向S的下一結點S’

第三步，把這個鏈表拆分成兩個鏈表

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include "stdafx.h"
  4 
  5 struct ComplexListNode
  6 {
  7     int                m_nValue;
  8     ComplexListNode*   m_pNext;
  9     ComplexListNode*   m_pSibling;
 10 };
 11 
 12 ComplexListNode* CreateNode(int nValue);
 13 void BuildNodes(ComplexListNode* pNode, ComplexListNode* pNext, ComplexListNode* pSibling);
 14 void PrintList(ComplexListNode* pHead);
 15 
 16 ComplexListNode* CreateNode(int nValue)
 17 {
 18     ComplexListNode* pNode = new ComplexListNode();
 19     
 20     pNode->m_nValue = nValue;
 21     pNode->m_pNext = NULL;
 22     pNode->m_pSibling = NULL;
 23     
 24     return pNode;
 25 }
 26 
 27 void BuildNodes(ComplexListNode* pNode, ComplexListNode* pNext, ComplexListNode* pSibling)
 28 {
 29     if(pNode != NULL)
 30     {
 31         pNode->m_pNext = pNext;
 32         pNode->m_pSibling = pSibling;
 33     }
 34 }
 35 
 36 void PrintList(ComplexListNode* pHead)
 37 {
 38     ComplexListNode* pNode = pHead;
 39     while(pNode != NULL)
 40     {
 41         printf("The value of this node is: %d.\n", pNode->m_nValue);
 42         
 43         if(pNode->m_pSibling != NULL)
 44             printf("The value of its sibling is: %d.\n", pNode->m_pSibling->m_nValue);
 45         else
 46             printf("This node does not have a sibling.\n");
 47         
 48         printf("\n");
 49         
 50         pNode = pNode->m_pNext;
 51     }
 52 }
 53 
 54 void CloneNodes(ComplexListNode* pHead);    //復制原始鏈表 
 55 void ConnectSiblingNodes(ComplexListNode* pHead); //設置復制出來的的結點的m_pSibling 
 56 ComplexListNode* ReconnectNodes(ComplexListNode* pHead);//拆分兩個鏈表 
 57 
 58 ComplexListNode* Clone(ComplexListNode* pHead)
 59 {
 60     CloneNodes(pHead);
 61     ConnectSiblingNodes(pHead);
 62     return ReconnectNodes(pHead);
 63 }
 64 
 65 //第一步 
 66 void CloneNodes(ComplexListNode* pHead)
 67 {
 68     ComplexListNode* pNode = pHead;
 69     while(pNode != NULL)
 70     {
 71         ComplexListNode* pCloned = new ComplexListNode();
 72         pCloned->m_nValue = pNode->m_nValue;
 73         pCloned->m_pNext = pNode->m_pNext;
 74         pCloned->m_pSibling = NULL;
 75         
 76         pNode->m_pNext = pCloned;
 77         
 78         pNode = pCloned->m_pNext;
 79     }
 80 }
 81 
 82 //第二步 
 83 void ConnectSiblingNodes(ComplexListNode* pHead)
 84 {
 85     ComplexListNode* pNode = pHead;
 86     while(pNode != NULL)
 87     {
 88         ComplexListNode* pCloned = pNode->m_pNext;
 89         if(pNode->m_pSibling != NULL)
 90         {
 91             pCloned->m_pSibling = pNode->m_pSibling->m_pNext;
 92         }
 93         
 94         pNode = pCloned->m_pNext;
 95     }
 96 }
 97 
 98 //第三步 
 99 ComplexListNode* ReconnectNodes(ComplexListNode* pHead)
100 {
101     ComplexListNode* pNode = pHead;
102     ComplexListNode* pClonedHead = NULL;
103     ComplexListNode* pClonedNode = NULL;
104     
105     if(pNode != NULL)
106     {
107         pClonedHead = pClonedNode = pNode->m_pNext;
108         pNode->m_pNext = pClonedNode->m_pNext;
109         pNode = pNode->m_pNext;
110     }
111     
112     while(pNode != NULL)
113     {
114         pClonedNode->m_pNext = pNode->m_pNext;
115         pClonedNode = pClonedNode->m_pNext;
116         
117         pNode->m_pNext = pClonedNode->m_pNext;
118         pNode = pNode->m_pNext;
119     }
120     
121     return pClonedHead;
122 }
123 
124 //          -----------------
125 //         \|/              |
126 //  1-------2-------3-------4-------5
127 //  |       |      /|\             /|\
128 //  --------+--------               |
129 //          -------------------------
130 
131 int main()
132 {
133     ComplexListNode* pNode1 = CreateNode(1);
134     ComplexListNode* pNode2 = CreateNode(2);
135     ComplexListNode* pNode3 = CreateNode(3);
136     ComplexListNode* pNode4 = CreateNode(4);
137     ComplexListNode* pNode5 = CreateNode(5);
138 
139     BuildNodes(pNode1,  pNode2,  pNode3);
140     BuildNodes(pNode2,  pNode3,  pNode4);
141     BuildNodes(pNode3,  pNode4,  NULL);
142     BuildNodes(pNode4,  pNode5,  pNode2);
143 
144     printf("The original list is:\n");
145     PrintList(pNode1);
146 
147     ComplexListNode*  pClonedHead = Clone(pNode1);
148 
149     printf("The cloned list is:\n");
150     PrintList(pClonedHead);
151 }