1 //复杂链表的复制 2 //输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 3 // 4 //思路：拷贝链表的结点，需要根据已知链表的结点的值，创建一个新的结点

5 struct RandomListNode 6 { 7     int label; 8     struct RandomListNode* next, *random; 9     RandomListNode(int x):label(x), next(NULL), random(NULL)10     {11 12     }13 };14 class Solution15 {16 public:17     RandomListNode* Clone(RandomListNode* pHead)18     {19         if (pHead == NULL)20         {21             return NULL;22         }23         ////第一步，创建结点然后并复制整个链表的结点---复制链表，需要遍历，因而需要创建链表的头结点24         RandomListNode* pNode=pHead;25         while(pNode != NULL)26         {27             RandomListNode* pCloned = new RandomListNode(pNode->label);28             pCloned->next = pNode->next;29             pNode->next = pCloned;30             pNode = pCloned->next;31         }32          //若原始链表上的结点N的m_pSibling指向S，则它对应的复制结点N'的m_pSibling指向S的下一个结点S'33         //第二步--再次对复制链表进行遍历34         RandomListNode* pNode1 = pHead;35         while(pNode1 != NULL)36         {37             RandomListNode* pCloned = pNode1->next;38             if (pNode1->random != NULL)39             {40                 pCloned->random = pNode1->random->next;41             }42             pNode1 = pCloned->next;43         }44         //第三步，将第二步得到的链表拆成两个链表，即奇数位置和偶数位置45         RandomListNode* pTmp = NULL;46         RandomListNode* pCurrentHead = pHead;47         RandomListNode* pClonedHead = pHead->next;48         //对复制链表进行拆分49         //-首先再循环备份两个链表的头结点，50         //然后循环判断条件就是头结点的下一个结点是否为NULL；51         //先备份下一个要遍历的结点，然后再做操作；再将备份结点改编成当前要处理的结点。52         while(pCurrentHead->next)53         {54             pTmp = pCurrentHead->next;55             pCurrentHead->next = pTmp->next;56             pCurrentHead = pTmp;57         }58         return pClonedHead;59     }60 };