1. 题目：

描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

示例:
输入:{1,2,3,4,5,3,5,#,2,#}
输出:{1,2,3,4,5,3,5,#,2,#}
解析:我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。
以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5
后半部分，3，5，#，2，#分别的表示为
1的位置指向3，2的位置指向5，3的位置指向nullptr，4的位置指向2，5的位置指向nullptr。
如下图:

示例一：

输入：
{1,2,3,4,5,3,5,#,2,#}
返回值：
{1,2,3,4,5,3,5,#,2,#}

2. 解法：

1. 哈希表：

/*
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;
        // 源-目标 的哈希表
        unordered_map<RandomListNode*, RandomListNode*> source_dest;

        while (cur != nullptr) {
            source_dest[cur] = new RandomListNode(cur->label);
            cur = cur->next;
        }

        // 重置头节点
        cur = pHead;
        while (cur != nullptr) {
            source_dest[cur]->next = source_dest[cur->next];
            source_dest[cur]->random = source_dest[cur->random];
            cur = cur->next;
        }

        return source_dest[pHead];
    }
};

2. 链表拼接，再拆分

/*
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;

        // 插入节点、拼接，只处理 next 节点
        int length = 0;
        while (cur != nullptr) {
            RandomListNode* tmp = cur;
            cur = cur->next;
            length++;

            tmp->next = new RandomListNode(tmp->label);
            tmp->next->next = cur;
        }

        // 处理 random 节点
        cur = pHead;
        while (cur != nullptr) {
            RandomListNode* tmp = cur;
            cur = cur->next->next;

            if (tmp->random != nullptr) {
                tmp->next->random = tmp->random->next;
            }
        }

        // 分离链表
        // 原始链表
        RandomListNode* sourceHead = pHead;
        RandomListNode* sourceCur = sourceHead;
        // 新链表
        RandomListNode* destHead = pHead->next;
        RandomListNode* destCur = destHead;
        for (int i = 0; i < length; i++) {
            // 原始链表
            sourceCur->next = destCur->next;
            sourceCur = sourceCur->next;

            // 新链表，需要判断最后一个节点是否为空
            if (destCur->next != nullptr) {
                destCur->next = sourceCur->next;
                destCur = destCur->next;
            }
        }

        return destHead;
    }

};