复杂链表的复制

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

【思路】第一个思路十分简单，使用一个hash_map来储存这些节点，key与value都是每个节点的地址，这样方便我们在遍历时获取这些节点，但是注意value是新建的节点，虽然其label一样，但地址是不同的！

遍历原来的链表，对hash_map的value中的next和random进行修改，修改后，返回其头节点即可！

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(pHead == nullptr)
            return nullptr;
        unordered_map<RandomListNode*, RandomListNode*> hash_map;
        RandomListNode* cur = pHead;
        while(cur != nullptr){
            RandomListNode* tmp = new RandomListNode(cur->label);
            hash_map[cur] = tmp;
            cur = cur->next;
        }
        cur = pHead;
        while(cur != nullptr){
            hash_map[cur]->next = hash_map[cur->next];
            hash_map[cur]->random = hash_map[cur->random];
            cur = cur->next;
        }
        return hash_map[pHead];
    }
};

当然，上面的方法虽然好理解，但是使用了额外的辅助空间hash_map，那么有没有不适用额外的空间复杂度的方法去实现呢？

1. 把复制的结点链接在原始链表的每一对应结点后面

2. 修改那些复制节点的random指针，怎么去寻找呢？其random指向为被复制节点的random指向的节点的next节点！

3. 将原链表与copy链表分离，主要就是修改next指针的指向，注意复制链表的最后一个结点的next指针不能跟原链表指向同一个空结点nullptr，next指针要重新赋值nullptr

   /*
   struct RandomListNode {
       int label;
       struct RandomListNode *next, *random;
       RandomListNode(int x) :
               label(x), next(NULL), random(NULL) {
       }
   };
   */
   class Solution {
   public:
       RandomListNode* Clone(RandomListNode* pHead)
       {
           if(pHead == nullptr)
               return nullptr;
           RandomListNode* cur = pHead;
           RandomListNode* pNext = nullptr;
           while(cur != nullptr){
               pNext = cur->next;
               cur->next = new RandomListNode(cur->label);
               cur->next->next = pNext;
               cur = pNext;  // 将每个节点进行拷贝
           }
           cur = pHead;
           // 设置拷贝节点的随机指针
           RandomListNode* copyNode = nullptr;
           while(cur != nullptr){
               pNext = cur->next->next;
               copyNode = cur->next;  // cur->random->next 就是cur->random的拷贝节点
               copyNode->random = ((cur->random != nullptr) ? cur->random->next : nullptr);
               cur = pNext;
           }
           cur = pHead;
           RandomListNode* res = pHead->next;
           while(cur != nullptr){
               pNext = cur->next->next;
               copyNode = cur->next;
               cur->next = pNext;
               copyNode->next = (pNext != nullptr) ? pNext->next : nullptr;
               cur = pNext;
           }
           return res;
       }
   };