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

解题思路

乍一看此题感觉不就是遍历链表，然后连接嘛，这样暴力解决的话肯定是可行的，但是我们不知道random出现在当前节点前面还是后面，导致不能一次遍历就能连接全部。

一种方法是保存节点与复制节点的成对的hash关系,根据`r = node->random`，去找对，就能快速找到node'对应的random节点。

不过，此种方式需要开辟O(N)大小的空间。

本题解采用另外一种方式，即大事化小策略，并且不用开辟额外空间。

把这个问题分解为三部分：

1. 复制节点，并且直接连接在当前被复制节点的后面，也就是说原来的head = [A, B, C]经过此操作后变为head = [A, A', B, B', C, C']

2. 给新复制的节点连接对应的random

3. 拆分head，返回copy，并且保持原head不变。

代码

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

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        copyNodes(pHead);
        connectRandom(pHead);
        return reconnect(pHead);
    }
private:
    /**
     * 复制每一个Node使之连接在当前被复制的Node后面。
     * @example head = [A, B, C], 操作后 head = [A, A', B, B', C, C']
     * @param head
     */
    void copyNodes(RandomListNode* head) {
        if (head == nullptr) return;
        RandomListNode* pHead = head;
        while (pHead != nullptr) {
            RandomListNode* cloned = new RandomListNode(pHead->label);
            cloned->next = pHead->next;
            pHead->next = cloned;
            pHead = cloned->next;
        }
    }
    /**
     * 连接random
     * @example A'->random = B'
     * @param head
     */
    void connectRandom(RandomListNode* head) {
        if (head == nullptr) return;
        RandomListNode* pHead = head;
        while (pHead != nullptr) {
            RandomListNode* cloned = pHead->next;
            if (pHead->random != nullptr)
                cloned->random = pHead->random->next;
            pHead = cloned->next;
        }
    }
    /**
     * 取head的偶数节点，重新连接为head'，并且head恢复为[A, B, C]
     * @example head = [A, A', B, B', C, C'] => head = [A, B, C], head' = [A', B', C']
     * @param head
     * @return head'
     */
    RandomListNode* reconnect(RandomListNode* head) {
        if (head == nullptr) return nullptr;
        RandomListNode* pHead = head;
        RandomListNode *copy = nullptr, *pNode = nullptr;
        if (pHead != nullptr) {
            copy = pNode = head->next; // copy = A'
            pHead = copy->next; // pHead = B;
            head->next = pHead; // head->next = B;
        }
        while (pHead != nullptr) {
            pNode->next = pHead->next; // A' -> next = B'
            pNode = pHead->next;
            pHead->next = pNode->next; // B->next = C;
            pHead = pHead->next;
        }
        return copy;
    }
};