https://leetcode.com/problems/copy-list-with-random-pointer/

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
	Node* copyRandomList(Node* head) {
		if (head == NULL) return head;
		
        Node* ori = head;
        Node* move = head;
        
        while(ori)
        {
            move = ori->next;
            Node* copy = new Node(ori->val);
            ori->next = copy;
            copy->next = move;
            ori = move;
        }
        
        ori = head;
        
        while(ori)
        {
            if(ori->random)
            {
                ori->next->random = ori->random->next;
            }
            ori = ori->next->next;
        }
        
        ori = head;
        Node* dummy = new Node(0);
        Node* output = dummy;
        
        while(ori)
        {
            move = ori->next->next;
            output->next = ori->next;
            ori->next = move;
            ori = move;
            output = output->next;
        }
        
		return dummy->next;
	}
};

Runtime: 4 ms, faster than 98.26% of C++ online submissions for Copy List with Random Pointer.

Memory Usage: 11.3 MB, less than 76.86% of C++ online submissions for Copy List with Random Pointer

Runtime: 8 ms, faster than 80.90% of C++ online submissions for Copy List with Random Pointer.

Memory Usage: 11.2 MB, less than 93.85% of C++ online submissions for Copy List with Random Pointer.