Copy List with Random Pointer — HashMap or Interleave

# Python
def copyRandomList(head):
    if not head: return None
    old_to_new = {None: None}
    cur = head
    while cur:
        old_to_new[cur] = Node(cur.val)
        cur = cur.next
    cur = head
    while cur:
        old_to_new[cur].next = old_to_new[cur.next]
        old_to_new[cur].random = old_to_new[cur.random]
        cur = cur.next
    return old_to_new[head]

# Python
def copyRandomList(head):
    if not head: return None
    # Step 1: Interleave copies
    cur = head
    while cur:
        copy = Node(cur.val)
        copy.next = cur.next
        cur.next = copy
        cur = copy.next
    # Step 2: Set random pointers
    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random.next
        cur = cur.next.next
    # Step 3: Separate lists
    old_head = head
    new_head = head.next
    cur_old = old_head; cur_new = new_head
    while cur_old:
        cur_old.next = cur_old.next.next
        cur_new.next = cur_new.next.next if cur_new.next else None
        cur_old = cur_old.next
        cur_new = cur_new.next
    return new_head

// Java — HashMap approach
public Node copyRandomList(Node head) {
    if (head == null) return null;
    Map<Node,Node> map = new HashMap<>();
    Node cur = head;
    while (cur != null) { map.put(cur, new Node(cur.val)); cur = cur.next; }
    cur = head;
    while (cur != null) {
        map.get(cur).next = map.get(cur.next);
        map.get(cur).random = map.get(cur.random);
        cur = cur.next;
    }
    return map.get(head);
}