//参考 https://www.cnblogs.com/edisonchou/p/4790090.html

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

不借助辅助空间的O(n)解法

class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        CloneNodes(head);
        ConnectSiblingNodes(head);
        return Reconnects(head);
    }
    void CloneNodes(ListNode* head){
        ListNode* node = head;
        while(node!=NULL){
            ListNode* cloned = new ListNode(node->val);
            cloned->next = node->next;

            node->next = cloned;
            node = cloned->next;
        }
    }
    void ConnectSiblingNodes(ListNode* head){
        ListNode* node = head;
        while(node!=NULL){
            ListNode* cloned = node->next;
            if(node->random!=NULL){
                cloned->random = node->random->next;
            }
            node = cloned->next;
        }
    }
    ListNode* Reconnects(ListNode* head){
        ListNode* node = head;
        ListNode* clonedHead = NULL;
        ListNode* clonedNode = NULL;

        if(node!=NULL){
            clonedHead = clonedNode = node->next;
            node->next = clonedNode->next;
            node = node->next;
        }
        while(node!=NULL){
            clonedNode->next = node->next;
            clonedNode = clonedNode->next;

            node->next = clonedNode->next;
            node = node->next;
        }
        return clonedHead;
    }
};