Copy linked list with random pointers efficiently

Given the head of a singly linked list where each node has next and random pointers, create a deep copy of the list. First provide an O(n) time, O(n) extra space solution using a hash map from original nodes to copies. Then implement an O(n) time, O( 1) extra space approach by interleaving copied nodes with original nodes, fixing random pointers, and restoring the original list. Discuss pitfalls such as null randoms, self-references, and cycles.