Copy list with random pointer

Each node of a singly linked list has a next pointer and a random pointer that may point to any node in the list or to nothing. Return a deep copy of the list in which no pointer refers to an original node. Do it first with a map from old nodes to new ones, then discuss the version that interleaves copies into the original list to use constant extra space.