复杂链表的复制

题目描述： 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个next指向下一个节点，另一个特殊指针random指向一个随机节点）， 请对此链表进行深拷贝，并返回拷贝后的头结点。

最近有人跟我提到这个问题，网上一搜原来是一个经典面试题。我的笨脑袋想不到最优解法，但是想到了两个常规解和一个带限制的解法。下面把这四种解法都列出来。

解法一：

先做正常拷贝，即next正确。然后同时遍历两个链表，对于原链表的每个结点，再同时遍历两个链表找到原random所在位置，也就有了新random所在位置。

时间复杂度为O(n^2)。

解法二：

先做正常拷贝，即next正确，同时建立一个哈希表<原结点，复制结点>。同时遍历两个链表，对于每一个复制结点，其random等于对应的原结点的random，在表中的映射。

时间复杂度大致为O(n)，因为哈希表通常很快。空间复杂度稍高。但是对于实际工程，这个哈希表通常可以复用，而且实现较有条理，容易理解，因此我认为在实际项目中这是最合适的解法。

解法三：

先做正常拷贝，即next正确，对于每个原结点，将其random指向对应的复制结点，而复制结点的random指向原结点的random。相当于是让复制结点充当一个桥接，复用原内存建立两个映射，并且没有丢失信息。

最后同时遍历两个链表，每一步都重建原结点和复制结点的random。

但是这个方法有个限制，必须前提保证random向后指，不能向前指，否则遍历的过程中也同时破坏映射，算法就会失效。

解法四：

这应该是最优解了：每次复制原结点，将复制结点插入其后，这样形成了一个长度2倍的复合链表。对于每一个复制结点，它的random为原结点的random的next。最后再把这个复合链表拆散还原。网上有详尽图文解释，这里不再赘述。

下面是C++代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unordered_map>

typedef int Data;

struct Node
{
    Data data;
    Node *next;
    Node *random;

    Node()
    {
        random = next = NULL;
        data = rand();
    }
};

Node *copy_method1(Node *list)
{
    Node *listCopy = NULL;

    Node *curr = list;
    Node *lastCopy = NULL;
    while (curr)
    {
        Node *currCopy = new Node;
        currCopy->data = curr->data;
        lastCopy ? lastCopy->next = currCopy : listCopy = currCopy;
        lastCopy = currCopy;
        curr = curr->next;
    }

    for (Node *curr = list, *currCopy = listCopy; curr; curr = curr->next, currCopy = currCopy->next)
    {
        if (curr->random)
        {
            for (Node *curr1 = list, *currCopy1 = listCopy; curr1; curr1 = curr1->next, currCopy1 = currCopy1->next)
                if (curr1 == curr->random)
                    currCopy->random = currCopy1;
        }
    }

    return listCopy;
}

Node *copy_method2(Node *list)
{
    // 1. Copy regular & make mapping
    Node *listCopy = NULL;
    Node *lastCopy = NULL;
    std::unordered_map<Node *, Node *> raw2Copy;
    for (Node *curr = list; curr; curr = curr->next)
    {
        Node *currCopy = new Node;
        currCopy->data = curr->data;
        raw2Copy.insert(std::make_pair(curr, currCopy));
        lastCopy ? lastCopy->next = currCopy : listCopy = currCopy;
        lastCopy = currCopy;
    }

    // 2. Eval random
    for (Node *curr = list, *currCopy = listCopy; curr; curr = curr->next, currCopy = currCopy->next)
        if (curr->random)
            currCopy->random = raw2Copy[curr->random];
    return listCopy;
}

Node *copy_method3(Node *list)
{
    Node *listCopy = NULL;
    Node *lastCopy = NULL;
    for (Node *curr = list; curr; curr = curr->next)
    {
        // 1. Copy regular
        Node *currCopy = new Node;
        currCopy->data = curr->data;
        lastCopy ? lastCopy->next = currCopy : listCopy = currCopy;

        // 2. Make bridge
        currCopy->random = curr->random;
        curr->random = currCopy;

        lastCopy = currCopy;
    }

    for (Node *curr = list, *currCopy = listCopy; curr; curr = curr->next, currCopy = currCopy->next)
    {
        // 3. Get copy's random
        curr->random = currCopy->random;
        if (currCopy->random)
            currCopy->random = currCopy->random->random;
    }

    return listCopy;
}

Node *copy_method4(Node *list)
{
    Node *listCopy = NULL;
    for (Node *curr = list; curr; curr = curr->next->next)
    {
        // 1. Insert
        Node *currCopy = new Node;
        currCopy->data = curr->data;
        currCopy->next = curr->next;
        curr->next = currCopy;

        if (listCopy == NULL)
            listCopy = currCopy;
    }

    for (Node *curr = list; curr; curr = curr->next->next)
    {
        // 2. Assign copy's random
        if (curr->random)
            curr->next->random = curr->random->next;
    }

    for (Node *curr = list; curr; curr = curr->next)
    {
        // 3. Split two lists
        Node *actualNext = curr->next->next;
        if (curr->next->next)
            curr->next->next = curr->next->next->next;
        curr->next = actualNext;
    }

    return listCopy;
}

Node *helper_genRandList()
{
    // Generate nodes
    static const int N = 10;
    Node *nodes[N];
    srand(time(NULL));
    for (int i = 0; i < N; i++)
        nodes[i] = new Node;

    // Make regular list
    for (int i = 0; i < N - 1; i++)
        nodes[i]->next = nodes[i + 1];

    // Assign random random
    for (int i = 0; i < N - 1; i++)
    {
        // nodes[i]->random = nodes[std::max(i + 1, rand() % N)];
        nodes[i]->random = nodes[rand() % N];
    }

    return nodes[0];
}

int helper_validate(Node *listA, Node *listB)
{
    while (listA && listB)
    {
        if (listA->data != listB->data)
            return 1;
        if (listA->random || listB->random)
        {
            if (listA->random->data != listB->random->data)
                return 2;
            if (listA->random == listB->random) // Copy is incomplete
                return 3;
        }
        listA = listA->next;
        listB = listB->next;
    }
    return 0;
}

void helper_printList(Node *list)
{
    printf("---------------\n");
    while (list)
    {
        printf("%d\n", list->data);
        if (list->random)
            printf("(random)%d\n", list->random->data);
        list = list->next;
    }
    printf("---------------\n");
}

int main()
{
    Node *list = helper_genRandList();
    printf("%d\n", helper_validate(list, copy_method1(list)));
    printf("%d\n", helper_validate(list, copy_method2(list)));
    printf("%d\n", helper_validate(list, copy_method3(list)));
    printf("%d\n", helper_validate(list, copy_method4(list)));
    return 0;
}