题目描述 [复制带随机指针的链表]

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

示例

解题思路一

• 复制原始链表上的每个结点N创建N'，然后把这些创建出来的结点用pNext连接起来。同时把<N,N'>的配对信息方法一个哈希表中；
• 设置复制链表中的每个结点的random指针，如果原始链表中结点N的random指向结点S，那么在复制链表中，对应的N'应该指向S'。

代码一

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;

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

class Solution {
    unordered_map<RandomListNode*, RandomListNode*> hashmap;
public:
    RandomListNode* CloneLink(RandomListNode* pHead){
        RandomListNode *newHead = new RandomListNode(0);
        RandomListNode *p=newHead;
        RandomListNode *temp;

        while(pHead){
            temp = new RandomListNode(pHead->label);
            p->next = temp;
            hashmap[pHead] = temp;
            pHead = pHead->next;
            p = p->next;
        }

        return newHead->next;
    }

    RandomListNode* Clone(RandomListNode* pHead){

        RandomListNode *newHead = CloneLink(pHead);
        RandomListNode *p = newHead;

        while(newHead){
            newHead->random = hashmap[pHead->random];
            pHead = pHead->next;
            newHead = newHead->next;
        }
        return p;
    }
};

int main(){
    RandomListNode *node1 = new RandomListNode(1);
    RandomListNode *node2 = new RandomListNode(2);
    RandomListNode *node3 = new RandomListNode(3);
    RandomListNode *node4 = new RandomListNode(4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = nullptr;
    node1->random = nullptr;
    node3->random = node1;
    Solution sol;
    RandomListNode *head = sol.Clone(node1);
    cout << head->label <<endl;

    return 0;
}

解题思路二

• 根据原始链表的每个结点N创建对应的N'，然后将N‘通过pNext接到N的后面；
• 设置复制出来的结点的random。假设原始链表上的N的random指向结点S，那么其对应复制出来的N'是N->pNext指向的结点，同样S'也是结点S->pNext指向的结点。
• 把长链表拆分成两个链表，把奇数位置的结点用pNext连接起来的就是原始链表，把偶数位置的结点通过pNext连接起来的就是复制链表。

代码二

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead){
        if(!pHead) return nullptr;
        RandomListNode *p = pHead;
        while(p){
            RandomListNode *temp = new RandomListNode(p->label);
            temp->next = p->next;
            p->next = temp;
            p = temp->next;
        }

        p = pHead;
        while(p){
            if(p->random)  p->next->random = p->random->next;
            p = p->next->next;
        }

        p = pHead;
        RandomListNode *copyHead = p->next;
        while (p){
            RandomListNode *temp = p->next;
            p->next = temp->next;
            if(temp->next)
                temp->next = temp->next->next;
            p = p->next;
        }

        return copyHead;
    }
};