题目描述

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

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

注意：

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

算法1

1. 在原链表每个节点后插入对前一个节点的复制

   1 2 3 4 5 ------> 1 1 2 2 3 3 4 4 5 5

2. 链接random
3. 链接复制后的链表，恢复原来链表

时间复杂度 $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) {
        for(auto p = head; p; p = p->next->next){
            auto t = new ListNode(p->val);
            t->next = p->next;
            p->next = t;
        }

        for(auto p = head; p; p = p->next->next){
            if(p->random)
            p->next->random = p->random->next;
        }
        auto dummy = new ListNode(-1), 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;
    }
};