Copy a linked list with random pointers

Each node of a linked list has a next pointer and a random pointer that can point at any node or nowhere. Make a deep copy of the list. Do it with a map from old nodes to new ones, then without extra space by weaving the copies between the original nodes and splitting them apart.