复制链表的复制

题目：

/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

基本思想：

分为三步：

复制原始链表的任意节点N并创建新节点N，再把N’链接到N的后面

设置复制出来的结点的random指针，即为原始链表N上的random的指针的next.

拆分链表，奇数位置的结点链接起来的链表就是复制的链表。

代码如下：

RandomListNode* Clone(RandomListNode* pHead) { if(pHead==NULL) return NULL; RandomListNode *pNode=pHead; //复制 while(pNode) { RandomListNode* pClonednode=new RandomListNode(pNode->label); pClonednode->next=pNode->next; pClonednode->random=NULL; pNode->next=pClonednode; pNode=pClonednode->next; } //复制random pNode=pHead; while(pNode) { RandomListNode* node=pNode->next; if(pNode->random) node->random=pNode->random->next; pNode=node->next; } //拆分，每隔一个结点拆一个 RandomListNode *pCloneHead=pHead->next; RandomListNode *CurNode=NULL; pNode=pHead; while(pNode->next) { CurNode=pNode->next; pNode->next=CurNode->next; pNode=CurNode; } return pCloneHead; }