题解： 复杂链表的复刻 【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;  )
        {
                auto new_p = new ListNode(p->val);  // 创建一个和p相同的节点
                auto c = p->next;
                p->next = new_p;
                new_p->next = c;
                p=c;
        }

        // 复制random节点
        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;
    }
};