题目描述

给定一个单链表，链表中的每个节点包含一个额外的指针，随机指向链表中的其它节点或者指向 null。
请复制整个链表，并返回新链表的头结点。

算法1

(recursive) $O(n^2)$

intuitively, 这个每个node有多个指针的链表很像一个图，所以最先想到的是图的遍历。用dfs recursively traverse这个图，clone每一个node。只不过->child这里是->next和->random。

时间复杂度分析：blablabla

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    unordered_map<Node*, Node*> visHash; //assigned outside otherwise stackoverflow
    Node* copyRandomList(Node* head) {
        if(!head) 
            return NULL;
        if(visHash.count(head))
            return visHash[head];
        Node* root = new Node(head->val, NULL, NULL);
        visHash[head] = root;
        root->next = copyRandomList(head->next);
        root->random = copyRandomList(head->random);
        return root;
    }
};

算法2

(iterative) $O(n)$

link the nodes inside the hash table

好像这题的def Node变了。写了个最新版本。

时间复杂度分析：遍历一遍，$O(n)$

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> hash;
        if(!head) 
            return NULL;
        Node* root = new Node(head->val, NULL, NULL);
        hash[head] = root;
        while(head->next){
            if(!hash.count(head->next)){
                hash[head->next] = new Node(head->next->val, NULL, NULL);
            }
            hash[head]->next = hash[head->next];
            if(head->random && !hash.count(head->random)){
                hash[head->random] = new Node(head->random->val, NULL, NULL);
            }
            hash[head]->random = hash[head->random];
            head = head->next;
        }
        if(head->random && !hash.count(head->random)){
            hash[head->random] = new Node(head->random->val, NULL, NULL);
        }
        hash[head]->random = hash[head->random];

        return root;

    }
};

算法3

(iterative with O(1) space) $O(n)$

不需要额外map存copy，in place修改input linked list，然后再restore。

1.copy each node. insert the copy node next to the corresponding original one.
2.traverse the list, copy the random ptr
3.restore the original list and return the new one

时间复杂度分析：$O(n)$

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)
            return head;
        Node* l1, *l2, *root;
        for(l1 = head; l1 ; l1 = l1->next->next){
            l2 = new Node(l1->val, NULL, NULL);
            l2->next = l1->next;
            l1->next = l2;
        }
        root = head->next;
        for(l1 = head; l1; l1 = l1->next->next){
            if(l1->random){
                l1->next->random = l1->random->next;
            }
        }
        for(l1 = head; l1;l1 = l1->next){
            l2 = l1->next;
            l1->next = l2->next;
            if(l2->next)
                l2->next = l2->next->next;
        }
        return root;
    }
};