1、题目描述

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

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

2、问题描述：

3、问题关键：

• 在每个结点后面插入一个和当前结点相同的结点，再，将插入的结点的random指针指向和原来对应的结点的下一个就可以了。

4、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) {
        if (!head) return head;
        auto p = head;
        while(p) {//在每个结点后面插入一个和当前结点相同的结点。
            auto tmp = new ListNode(p->val);
            auto t = p->next;
            p->next = tmp;
            tmp->next = t;
            p = t;
        }
        p = head;
        while(p) {//将新的结点的random指针指向原结点的random指针的下一个结点。
            if (p->random) 
                p->next->random = p->random->next;
            p = p->next->next;
        }
        p = head;
        ListNode *dummy = new ListNode(-1);
        auto cur = dummy;
        while(p) {//断开结点，提取出新建的结点。
            cur->next = p->next;
            cur = cur->next;
            p = cur->next;
        }
        return dummy->next;
    }
};