Copy list with random pointers

You are given the head of a singly linked list where each node has two pointers: next and random (random may point to any node or be null). Construct a deep copy of the list and return the head of the copied list. Aim for O(n) time and O( 1) extra space beyond the new nodes by weaving/unweaving or an equivalent technique. Explain how you preserve random relationships and how you would verify correctness with corner cases such as cycles via random, single-node lists, and all-random-null.