https://leetcode.com/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-interview-150

def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
	def getNodeCopy(node):
	    if not node: return None
	    if node not in copies:
	        copies[node] = Node(x=node.val)
	    return copies[node]
	
	copies = {}
	dummy = getNodeCopy(head)
	while head:
	    curr_copy = getNodeCopy(head)
	    curr_copy.next = getNodeCopy(head.next)
	    curr_copy.random = getNodeCopy(head.random)
	    head = head.next
	return dummy

Time Complexity: O(N) - We traverse through each node in the linked list once

Space Complexity: O(N) - We use a hash map (copies) that stores a copy of each node

While it's true that we typically don't count the space needed for the output, this solution uses a hash map (copies) as extra space to store the node mappings during the algorithm's execution. This additional data structure is necessary for the algorithm to work properly and is separate from the output space.

/*
// 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:
    map<Node*, Node*> copies;
    Node* getNodeCopy(Node* node){
        if (node == nullptr) return nullptr;
        if (copies.find(node) == copies.end()){
            Node* new_node = new Node(node->val);
            copies[node] = new_node;
        }
        return copies[node];
    }
    Node* copyRandomList(Node* head) {
        Node* new_head = getNodeCopy(head);
        while (head){
            Node* curr_copy = getNodeCopy(head);
            curr_copy->next = getNodeCopy(head->next);
            curr_copy->random = getNodeCopy(head->random);
            head = head->next;
        }
        return new_head;
    }
};