题目描述

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

函数结束后原链表要与输入时保持一致。

算法1

(hash) $O(n)$

参考文献

https://www.acwing.com/solution/content/2168/

C++ 代码

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        auto dummy = new ListNode(0);
        if(!head) return dummy->next;

        unordered_map<ListNode*, ListNode*>hash;
        hash[nullptr] = nullptr;
        auto cur = head, n_cur = dummy;

        while(cur){
            if(hash.find(cur) == hash.end()) hash[cur] = new ListNode(cur->val);
            if(hash.find(cur->random) == hash.end()) hash[cur->random] = new ListNode(cur->random->val);  //空指针创建错误，先将空指针加入到哈希表中

            n_cur->next =  hash[cur];
            n_cur->next->random = hash[cur->random];

            cur = cur->next;
            n_cur = n_cur->next;
        }
        return dummy->next;
    }
};

算法2

() $O(n)$

C++ 代码

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        auto dummy = new ListNode(0);
        if(!head) return dummy->next;

        auto cur = head, n_cur = dummy;
        while(cur){
            auto tmp = new ListNode(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = cur->next->next;
        }
        cur = head;
        while(cur){
            if(cur->random) cur->next->random = cur->random->next;
            cur = cur->next->next;
        }

        cur = head;
        while(cur){
            n_cur->next = cur->next; //取出复制的链表
            n_cur = n_cur->next;

            cur->next = cur->next->next;//还原原来的链表
            cur = cur->next;
        }

        return dummy->next;
    }
};