【链表】复杂链表的复制

 3 
 4 /*
 5 *解题思路：
 6 *1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
 7 *2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
 8 *3、拆分链表，将链表拆分为原链表和复制后的链表
 9 */
10 public class Solution {
11     public RandomListNode Clone(RandomListNode pHead) {
12         if(pHead == null) {
13             return null;
14         }
15          
16         RandomListNode currentNode = pHead;
17         //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
18         while(currentNode != null){
19             RandomListNode cloneNode = new RandomListNode(currentNode.label);
20             RandomListNode nextNode = currentNode.next;
21             currentNode.next = cloneNode;
22             cloneNode.next = nextNode;
23             currentNode = nextNode;
24         }
25          
26         currentNode = pHead;
27         //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
28         while(currentNode != null) {
29             currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
30             currentNode = currentNode.next.next;
31         }
32          
33         //3、拆分链表，将链表拆分为原链表和复制后的链表
34         currentNode = pHead;
35         RandomListNode pCloneHead = pHead.next;
36         while(currentNode != null) {
37             RandomListNode cloneNode = currentNode.next;
38             currentNode.next = cloneNode.next;
39             cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
40             currentNode = currentNode.next;
41         }
42          
43         return pCloneHead;
44     }
45 }

 3 
 4 /*
 5 struct RandomListNode {
 6     int label;
 7     struct RandomListNode *next, *random;
 8     RandomListNode(int x) :
 9             label(x), next(NULL), random(NULL) {
10     }
11 };
12 */
13 class Solution {
14 public:
15     //复制原始链表的任一节点N并创建新节点N‘，再把N‘链接到N的后边
16     void CloneNodes(RandomListNode* pHead)
17     {
18         RandomListNode* pNode=pHead;
19         while(pNode!=NULL)
20         {
21             RandomListNode* pCloned=new RandomListNode(0);
22             pCloned->label=pNode->label;
23             pCloned->next=pNode->next;
24             pCloned->random=NULL;
25               
26             pNode->next=pCloned;
27               
28             pNode=pCloned->next;
29         }
30     }
31     //如果原始链表上的节点N的random指向S，则对应的复制节点N‘的random指向S的下一个节点S‘
32     void ConnectRandomNodes(RandomListNode* pHead)
33     {
34         RandomListNode* pNode=pHead;
35         while(pNode!=NULL)
36         {
37             RandomListNode* pCloned=pNode->next;
38             if(pNode->random!=NULL)
39                 pCloned->random=pNode->random->next;
40             pNode=pCloned->next;
41         }
42     }
43     //把得到的链表拆成两个链表，奇数位置上的结点组成原始链表，偶数位置上的结点组成复制出来的链表
44     RandomListNode* ReConnectNodes(RandomListNode* pHead)
45     {
46         RandomListNode* pNode=pHead;
47         RandomListNode* pClonedHead=NULL;
48         RandomListNode* pClonedNode=NULL;
49           
50         //初始化
51         if(pNode!=NULL)
52         {
53             pClonedHead=pClonedNode=pNode->next;
54             pNode->next=pClonedNode->next;
55             pNode=pNode->next;
56               
57         }
58         //循环
59         while(pNode!=NULL)
60         {
61             pClonedNode->next=pNode->next;
62             pClonedNode=pClonedNode->next;
63             pNode->next=pClonedNode->next;
64             pNode=pNode->next;
65         }
66           
67         return pClonedHead;
68           
69     }
70     //三步合一
71     RandomListNode* Clone(RandomListNode* pHead)
72     {
73         CloneNodes(pHead);
74         ConnectRandomNodes(pHead);
75         return ReConnectNodes(pHead);
76     }
77 };