复杂链表的复刻，每个链表的有一个除了一个next结点之外，还有一个随便指向任何地方的random结点，刚开始写的时候，我直接对每个节点都新建了节点，这样对于next指针来说，无环的话是没有什么问题的，不过如果对于random指针的话，有可能存在原链表两个点的random节点指向的是一个节点，新创建的指向的是两个一模一样的节点，这两个节点的地址是不一样的，就会出现问题。时间复杂度$o(n)$，空间复杂度$o(n)$

/**
 * 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) {

        unordered_map<ListNode*,ListNode*>mp;
        mp[nullptr]=nullptr;
        ListNode *thead=head;
        ListNode *uhead=new ListNode(1e9);
        ListNode *uuhead = uhead;

        while(thead!=NULL)
        {
            if(!mp.count(thead))mp[thead]=new ListNode(thead->val);
            if(!mp.count(thead->random))mp[thead->random]=new ListNode(thead->random->val);


            uhead->next = mp[thead];
            uhead->next->random = mp[thead->random];
            // ListNode *temp = new ListNode(thead->val);

            // uhead->next=temp;
            // if(thead->random==NULL)
            // {
            //     uhead->random=NULL;
            // }
            // else
            // {
            //     uhead->random=new ListNode(thead->random->val);
            // }


            uhead=uhead->next;
            thead=thead->next;
        }

        return uuhead->next;
    }
};

算法2:不用哈希表的一个算法。

class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        for (auto p = head; p;)
        {
            auto np = new ListNode(p->val);
            auto next = p->next;
            p->next = np;
            np->next = next;
            p = next;
        }

        for (auto p = head; p; p = p->next->next)
        {
            if (p->random)
                p->next->random = p->random->next;
        }

        auto dummy = new ListNode(-1);
        auto cur = dummy;
        for (auto p = head; p; p = p->next)
        {
            cur->next = p->next;
            cur = cur->next;
            p->next = p->next->next;
        }

        return dummy->next;
    }
};