本文共 1455 字，大约阅读时间需要 4 分钟。

《剑指offer》刷题笔记7

1. 学习内容

   复杂链表的复制
   （1）思路
   逐个复制结点的值域和next指针域，并把复制的结点放在被复制的结点后面。
   复制当前结点的random域，付给下一结点。
   编号为奇数的结点为原链表结点，剩下的是复制出的新链表节点。
   （2）代码
   /*
   struct RandomListNode {
   int label;
   struct RandomListNode next, random;
   RandomListNode(int x) :
   label(x), next(NULL), random(NULL) {
   }
   };
   /
   class Solution {
   public:
   //第一步，复制复杂指针的label和next
   void CloneNodes(RandomListNode pHead){
   RandomListNode pNode = pHead;
   while(pNode != NULL){
   RandomListNode pCloned = new RandomListNode(0);
   pCloned->label = pNode->label;
   pCloned->next = pNode->next;
   pCloned->random = NULL;

   pNode->next = pCloned;    pNode = pCloned->next;}

   }

   //第二步，处理复杂指针的random

   void ConnectSiblingNodes(RandomListNode* pHead){
   RandomListNode* pNode = pHead;
   while(pNode != NULL){
   RandomListNode* pCloned = pNode->next;
   if(pNode->random != NULL){
   pCloned->random = pNode->random->next;
   }
   pNode = pCloned->next;
   }
   }

   //第三步，拆分复杂指针

   RandomListNode* ReconnectNodes(RandomListNode* pHead){
   RandomListNode* pNode = pHead;
   RandomListNode* pClonedHead = NULL;
   RandomListNode* pClonedNode = NULL;

   if(pNode != NULL){    pClonedHead = pClonedNode = pNode->next;    pNode->next = pClonedNode->next;    pNode = pNode->next;}while(pNode != NULL){    pClonedNode->next = pNode->next;    pClonedNode = pClonedNode->next;    pNode->next = pClonedNode->next;    pNode = pNode->next;}return pClonedHead;

   }

   RandomListNode* Clone(RandomListNode* pHead)

   {
   CloneNodes(pHead);
   ConnectSiblingNodes(pHead);
   return ReconnectNodes(pHead);
   }
   };

2. 参考网站