剑指offer第二十六题：复杂链表的复制
1 //============================================================================ 2 // Name : JZ-C-26.cpp 3 // Author : Laughing_Lz 4 // Version : 5 // Copyright : All Right Reserved 6 // Description : 复杂链表的复制 7 //============================================================================ 8 9 #include10 #include "ComplexList.h" 11 #include 12 using namespace std; 13 14 void CloneNodes(ComplexListNode* pHead); 15 void ConnectSiblingNodes(ComplexListNode* pHead); 16 ComplexListNode* ReconnectNodes(ComplexListNode* pHead); 17 18 ComplexListNode* Clone(ComplexListNode* pHead) { 19 CloneNodes(pHead); 20 ConnectSiblingNodes(pHead); 21 return ReconnectNodes(pHead); 22 } 23 /** 24 *第一步：克隆Next结点 25 */ 26 void CloneNodes(ComplexListNode* pHead) { 27 ComplexListNode* pNode = pHead; 28 while (pNode != NULL) { 29 ComplexListNode* pCloneNode = new ComplexListNode(); 30 pCloneNode->m_nValue = pNode->m_nValue; 31 pCloneNode->m_pNext = pNode->m_pNext; 32 pNode->m_pNext = pCloneNode; 33 pNode = pCloneNode->m_pNext; //进行下一次Clone 34 } 35 } 36 /** 37 *第二步：连接Sibling结点 38 */ 39 void ConnectSiblingNodes(ComplexListNode* pHead) { 40 ComplexListNode* pNode = pHead; 41 while (pNode != NULL) { 42 ComplexListNode* pCloneNode = pNode->m_pNext; 43 if (pNode->m_pSibling != NULL) { 44 pCloneNode->m_pSibling = pNode->m_pSibling->m_pNext; 45 } 46 pNode = pCloneNode->m_pNext; 47 } 48 } 49 /** 50 *第三步：拆分出复制的复杂链表 51 */ 52 ComplexListNode* ReconnectNodes(ComplexListNode* pHead) { 53 ComplexListNode* pNode = pHead; 54 ComplexListNode* pCloneHead = NULL; 55 ComplexListNode* pCloneNode = NULL; 56 if (pNode != NULL) { 57 pCloneHead = pCloneNode = pNode->m_pNext; //先确定复制链表的头 58 pNode = pCloneNode->m_pNext; 59 } 60 while (pNode != NULL) { 61 pCloneNode->m_pNext = pNode->m_pNext; 62 pCloneNode = pCloneNode->m_pNext; 63 pNode = pCloneNode->m_pNext; 64 } 65 return pCloneHead; 66 } 67 68 // ====================测试代码==================== 69 void Test(char* testName, ComplexListNode* pHead) { 70 if (testName != NULL) 71 printf("%s begins:\n", testName); 72 73 printf("The original list is:\n"); 74 PrintList(pHead); 75 76 ComplexListNode* pClonedHead = Clone(pHead); 77 78 printf("The cloned list is:\n"); 79 PrintList(pClonedHead); 80 } 81 82 // ----------------- 83 // \|/ | 84 // 1-------2-------3-------4-------5 85 // | | /|\ /|\ 86 // --------+-------- | 87 // ------------------------- 88 void Test1() { 89 ComplexListNode* pNode1 = CreateNode(1); 90 ComplexListNode* pNode2 = CreateNode(2); 91 ComplexListNode* pNode3 = CreateNode(3); 92 ComplexListNode* pNode4 = CreateNode(4); 93 ComplexListNode* pNode5 = CreateNode(5); 94 95 BuildNodes(pNode1, pNode2, pNode3); 96 BuildNodes(pNode2, pNode3, pNode5); 97 BuildNodes(pNode3, pNode4, NULL); 98 BuildNodes(pNode4, pNode5, pNode2); 99 100 Test("Test1", pNode1);101 }102 103 // m_pSibling指向结点自身104 // -----------------105 // \|/ |106 // 1-------2-------3-------4-------5107 // | | /|\ /|\108 // | | -- |109 // |------------------------|110 void Test2() {111 ComplexListNode* pNode1 = CreateNode(1);112 ComplexListNode* pNode2 = CreateNode(2);113 ComplexListNode* pNode3 = CreateNode(3);114 ComplexListNode* pNode4 = CreateNode(4);115 ComplexListNode* pNode5 = CreateNode(5);116 117 BuildNodes(pNode1, pNode2, NULL);118 BuildNodes(pNode2, pNode3, pNode5);119 BuildNodes(pNode3, pNode4, pNode3);120 BuildNodes(pNode4, pNode5, pNode2);121 122 Test("Test2", pNode1);123 }124 125 // m_pSibling形成环126 // -----------------127 // \|/ |128 // 1-------2-------3-------4-------5129 // | /|\130 // | |131 // |---------------|132 void Test3() {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, NULL);140 BuildNodes(pNode2, pNode3, pNode4);141 BuildNodes(pNode3, pNode4, NULL);142 BuildNodes(pNode4, pNode5, pNode2);143 144 Test("Test3", pNode1);145 }146 147 // 只有一个结点148 void Test4() {149 ComplexListNode* pNode1 = CreateNode(1);150 BuildNodes(pNode1, NULL, pNode1);151 152 Test("Test4", pNode1);153 }154 155 // 鲁棒性测试156 void Test5() {157 Test("Test5", NULL);158 }159 160 int main(int argc, char** argv) {161 Test1();162 Test2();163 Test3();164 Test4();165 Test5();166 167 return 0;168 }