题解 | #复杂链表的复制#

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
      //map
      //if (pHead == nullptr) return nullptr;
      // 1:1' 2:2' 3:3'
//       unordered_map<RandomListNode*, RandomListNode*> map;
//       RandomListNode* cur = pHead;
//       while (cur != nullptr) {
//         map[cur] = new RandomListNode(cur->label);//1:1' 2:2' 3:3'
//         cur = cur->next;
//       }
//       cur = pHead;
//       while (cur != nullptr) {
//         map[cur]->next = map[cur->next];
//         map[cur]->random = map[cur->random];
//         cur = cur->next;
//       }
//       return map[pHead];
      
      //有限几个变量解决
      //==================================================================================
      if (pHead == nullptr) return nullptr;
      RandomListNode* cur = pHead;
      RandomListNode* next = nullptr;
      //先拷贝为1->1'->2->2'->3->3'->null这种形式，然后在这个上面进行操作
      while (cur != nullptr) {
        next = cur->next;
        cur->next = new RandomListNode(cur->label);
        cur->next->next = next;
        cur = next;
      }
      //random指针已操作完毕
      cur = pHead;
      RandomListNode* curCopy = nullptr;
      while (cur != nullptr) {
        next = cur->next->next;
        curCopy = cur->next; 
        curCopy->random = cur->random != nullptr ? cur->random->next : nullptr;
        cur = next;
      }
      // 把带有随机指针的1->1'->2->2'->3->3'->null　分离成１->2->3和带有随机指针的1'->2'->3'
      cur = pHead;
      RandomListNode* res = pHead->next;
      while (cur != nullptr) {
        next = cur->next->next;
        curCopy = cur->next;
        curCopy->next =  next != nullptr ? next->next : nullptr;
        cur->next = next;
        cur = next;
      }
      return res;
      
      
      
      
      
      
      
      
      
      
      
      
      
        
    }
};