※剑指offer系列19：复杂链表的复制

这道题是典型的分治法，将一个大问题分解成几小步解决。一定要注意在使用指针的时候指针指向是否为空的问题。在指针指向时，可以将一个指向为空的指针作为赋值来写，但是空指针不能指向任何地方（指向空也不行），这点一定要记住。

  1 #include<iostream>
  2 #include<vector>
  3 using namespace std;
  4 struct RandomListNode {
  5 int label;
  6 struct RandomListNode *next, *random;
  7 /*
  8 RandomListNode(int x) :
  9 label(x), next(NULL), random(NULL) {
 10 }
 11 */
 12 };
 13 
 14 class Solution {
 15 public:
 16     RandomListNode* Clone(RandomListNode* pHead)
 17     {
 18         if (pHead == NULL)
 19             return NULL;
 20         //3步
 21         //第一步，将复杂链表复制成double
 22         nodeclone(pHead);
 23         connect(pHead);
 24         return reconnect(pHead);
 25     }
 26     void nodeclone(RandomListNode* Head)
 27     {
 28         RandomListNode*p = Head;
 29         while (p != NULL)
 30         {
 31             //插入节点
 32             //cur = p->next;
 33             RandomListNode *curnode = new RandomListNode();
 34             curnode->label = p->label;
 35             curnode->next = p->next;
 36             curnode->random = NULL;//这一句必须要写？
 37             p->next = curnode;
 38             p = curnode->next;//悬浮指针？
 39         }
 40     }
 41     void connect(RandomListNode* Head)
 42     {
 43         //第二步：将复制出的结点的随机指针指向该有的位置
 44         RandomListNode*p = Head;
 45         while (p != NULL)//在指针访问的时候，时刻注意是否为空
 46         {
 47             RandomListNode *curnode = p->next;
 48 
 49             if (p->random != NULL)
 50             {
 51                 curnode->random = p->random->next;
 52             }
 53 
 54             p = curnode->next;
 55 
 56         }
 57     }
 58     RandomListNode *reconnect(RandomListNode* Head)
 59     {
 60         //第三步：将链表拆为两部分
 61         RandomListNode*p = Head;
 62         RandomListNode *copy = p->next;
 63         while (p!= NULL)
 64         {
 65             RandomListNode *curnode = p->next;
 66             if (curnode != NULL)
 67             {
 68                 p->next = curnode->next;
 69             }
 70         
 71             p = curnode;
 72         }
 73         return copy;
 74     }
 75 };
 76 int main()
 77 {
 78     RandomListNode list[5];
 79     list[0].label = 1;
 80     list[0].next = &list[1];
 81     list[0].random = &list[2];
 82 
 83     list[1].label = 2;
 84     list[1].next = &list[2];
 85     list[1].random = &list[4];
 86 
 87     list[2].label = 3;
 88     list[2].next = &list[3];
 89     list[2].random = NULL;
 90 
 91     list[3].label = 4;
 92     list[3].next = &list[4];
 93     list[3].random = &list[1];
 94 
 95     list[4].label = 5;
 96     list[4].next =NULL;
 97     list[4].random = NULL;
 98 
 99     Solution solu;
100     RandomListNode *re = solu.Clone(list);
101     int count=0;
102     while (re != NULL)
103     {
104         //cout << re->label << " "<<re->random->label<<",";
105         cout << re->label<<" ";
106         if (re->random != NULL)
107             cout << re->random->label;
108         cout << endl;
109         count++;
110         re = re->next;
111     }
112     //cout << endl;
113     cout << "number of array:"<<count << endl;
114     return 0;
115 }

之前把这篇写在另一个博客了，现在补回来。