1 /*************************************************************************  2     > File Name: 24_ComplexListClone.cpp  3     > Author: Juntaran  4     > Mail: JuntaranMail@gmail.com  5     > Created Time: 2016年08月31日 星期三 14时24分35秒  6  ************************************************************************/  7   8 #include <stdio.h>  9 #include <malloc.h> 10  11 // 链表结构体 12 struct ComplexListNode 13 { 14     int val; 15     ComplexListNode* next; 16     ComplexListNode* rand; 17 }; 18  19 // 构造链表 20 ComplexListNode* createList() 21 { 22     ComplexListNode* A = new ComplexListNode(); 23     ComplexListNode* B = new ComplexListNode(); 24     ComplexListNode* C = new ComplexListNode(); 25     ComplexListNode* D = new ComplexListNode(); 26     ComplexListNode* E = new ComplexListNode(); 27     A->val  = 1; 28     A->next = B; 29     A->rand = C; 30     B->val  = 2; 31     B->next = C; 32     B->rand = E; 33     C->val  = 3; 34     C->next = D; 35     C->rand = NULL; 36     D->val  = 4; 37     D->next = E; 38     D->rand = B; 39     E->val  = 5; 40     E->next = NULL; 41     E->rand = NULL; 42      43     return A; 44 } 45  46 void* PrintComplexList(ComplexListNode* head) 47 { 48     while (head) 49     { 50         if (head->rand != NULL) 51             printf("%d rand=%d\n", head->val, head->rand->val); 52         else 53             printf("%d\n", head->val); 54         head = head->next; 55     } 56     printf("\n"); 57 } 58  59 // 复制链表，复制的接在原位置后面 60 void CloneNodes(ComplexListNode* head) 61 { 62     ComplexListNode* node = head; 63     while (node != NULL) 64     { 65         ComplexListNode* newNode = new ComplexListNode(); 66         newNode->val = node->val; 67         newNode->next = node->next; 68         newNode->rand = NULL; 69         node->next = newNode; 70         node = newNode->next; 71     } 72 } 73  74 // 补充复制的链表的rand指针 75 void AddRand(ComplexListNode* head) 76 { 77     ComplexListNode* node = head; 78     while (node != NULL) 79     { 80         ComplexListNode* newNode = node->next; 81         if (node->rand != NULL) 82             newNode->rand = node->rand->next; 83         node = newNode->next; 84     } 85 } 86  87 // 拆分链表 88 ComplexListNode* SplitList(ComplexListNode* head) 89 { 90     ComplexListNode* node = head; 91     ComplexListNode* newHead = NULL; 92     ComplexListNode* newNode = NULL; 93      94     if (node != NULL) 95     { 96         newHead = newNode = node->next; 97         node->next = newNode->next; 98         node = node->next; 99     }100     while (node != NULL)101     {102         newNode->next = node->next;103         newNode = newNode->next;104         node->next = newNode->next;105         node = node->next;106     }107     return newHead;108 }109 110 ComplexListNode* Clone(ComplexListNode* head)111 {112     CloneNodes(head);113     AddRand(head);114     return SplitList(head);115 }116 117 int main()118 {119     ComplexListNode* test = createList();120     PrintComplexList(test);121     122     ComplexListNode* newTest = Clone(test);123     PrintComplexList(test);124     PrintComplexList(newTest);125     126 }