Clone a linked list with a random pointer

I'm working on a problem to clone a linked list (each node has a regular next pointer), and each node also has a random pointer which could point to any node in the linked list. Each linked list node has a unique ID and new cloned linked list node should have the same node ID.

One major concern in my current implementation is that I create another randomMap to map from a newly cloned linked list node ID to a newly cloned linked list node. I'm wondering if you have any ideas on saving the mapping (so that the additional \$O(n)\$ space could be saved).

```
from __future__ import print_function
from collections import defaultdict

class LinkedListNode:
def __init__(self, nodeID):
self.nodeID = nodeID
self.nextNode = None
self.randomNode = None
def dump(self):
node = self
print (node.nodeID, node.nextNode.nodeID if node.nextNode else -1, node.randomNode.nodeID if node.randomNode else -1)
node = self.nextNode
while node:
print (node.nodeID, node.nextNode.nodeID if node.nextNode else -1, node.randomNode.nodeID if node.randomNode else -1)
node = node.nextNode
def cloneList(self):
node = self
randomMap = defaultdict(LinkedListNode) # key node ID, value LinkedListNode in new list
preNode = LinkedListNode(node.nodeID)
randomMap[node.nodeID] = preNode
head = preNode
# setup regular part
while node.nextNode:
curNode = LinkedListNode(node.nextNode.nodeID)
randomMap[node.nextNode.nodeID] = curNode
preNode.nextNode = curNode
preNode = curNode
node = node.nextNode
# setup up random part
node = self
while node:
randomMap[node.nodeID].randomNode=randomMap[node.randomNode.nodeID]
node = node.nextNode

return head

if __name__ == "__main__":
node1 = LinkedListNode('1')
node2 = LinkedListNode('2')
node3 = Linked

It is indeed possible to spare the map, by the cost of an additional linear pass. A key is to create a cloned list not independently, but interleaved with the original one:

while node:
        image = LinkedListNode(node.ID)
        image.next = node.next
        node.next = image
        node = image.next

The second pass sets up the random pointers in the cloned nodes:

while node:
        image = node.next
        image.random = node.random.next
        node = image.next

And the final pass disconnects interleaved lists:

try:
        while True:
            image = node.next
            node.next = image.next
            image.next = image.next.next
            node = node.next
    except ValueError:
        pass

The exception comes from the last node: image.next is None.

StackExchange Code Review Q#143869, answer score: 2