面试题26 复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。
 1 /*
 2 struct RandomListNode {
 3     int label;
 4     struct RandomListNode *next, *random;
 5     RandomListNode(int x) :
 6             label(x), next(NULL), random(NULL) {
 7     }
 8 };
 9 */
10 class Solution {
11 public:
12     void CloneNodes(RandomListNode *pHead){
13         RandomListNode *pNode = pHead;
14         while (pNode != NULL){
15             RandomListNode *pClone = new RandomListNode(pNode->label);
16             pClone->next = pNode->next;
17             pClone->random = NULL;
18             pNode->next = pClone;
19             pNode = pClone->next;
20         }
21     }
22     
23     void ConnectRandomNodes(RandomListNode *pHead){
24         RandomListNode *pNode = pHead;
25         while (pNode != NULL){
26             RandomListNode *pClone = pNode->next;
27             if (pNode->random != NULL){
28                 pClone->random = pNode->random->next;
29             }
30             pNode = pClone->next;
31         }
32     }
33     
34     RandomListNode* ReconnectNodes(RandomListNode *pHead){
35         RandomListNode *pNode = pHead;
36         RandomListNode *pCloneHead = NULL;
37         RandomListNode *pCloneNode = NULL;
38         
39         if (pNode != NULL){
40             pCloneHead = pCloneNode = pNode->next;
41             pNode->next = pCloneHead->next;
42             pNode = pNode->next;
43         }
44         
45         while (pNode != NULL){
46             pCloneNode->next = pNode->next;
47             pCloneNode = pCloneNode->next;
48             pNode->next = pCloneNode->next;
49             pNode = pNode->next;
50         }
51         return pCloneHead;
52     }
53     
54     
55     RandomListNode* Clone(RandomListNode* pHead)
56     {
57         CloneNodes(pHead);
58         ConnectRandomNodes(pHead);
59         return ReconnectNodes(pHead);
60     }
61 };