题目:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。
复杂链表的结构如下:
1 struct RandomListNode {2 int label;3 struct RandomListNode *next, *random;4 RandomListNode(int x) :5 label(x), next(NULL), random(NULL) {6 }7 };
代码如下:
1 RandomListNode* Clone(RandomListNode* pHead){ 2 if(!pHead) return NULL; 3 RandomListNode *currNode = pHead; 4 //复制原始链表的任意节点N并创建新节点N',并把N'连接到N的后面 5 while(currNode){ 6 RandomListNode *node = new RandomListNode(currNode->label); 7 node->next = currNode->next; 8 currNode->next = node; 9 currNode = node->next;10 }11 currNode = pHead;12 13 //如果原始链表上的节点N的random指向S,则它对应的复制节点N'的random指向S的下一个节点S'14 while(currNode){15 RandomListNode *node = currNode->next;16 if(currNode->random){ 17 node->random = currNode->random->next;18 }19 currNode = node->next;20 }21 //把第二步得到的链表拆分成两个链表,奇数位置上的节点组成原始链表,偶数位置上的节点组成复制出来的链表22 RandomListNode *pCloneHead = pHead->next;23 RandomListNode *tmp;24 currNode = pHead;25 while(currNode->next){26 tmp = currNode->next;27 currNode->next =tmp->next;28 currNode = tmp;29 }30 return pCloneHead;31 }