Clone a linked list with a random pointer

Question

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 = LinkedListNode('3')
 node4 = LinkedListNode('4')
 node5 = LinkedListNode('5')
 node1.nextNode = node2
 node2.nextNode = node3
 node3.nextNode = node4
 node4.nextNode = node5
 node1.randomNode = node3
 node2.randomNode = node4
 node3.randomNode = node5
 node4.randomNode = node1
 node5.randomNode = node2
 newList = node1.cloneList()
 newList.dump()

Expected output

1 2 3
2 3 4
3 4 5
4 5 1
5 -1 2

Answer 1

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.

• Lin Ma: This method is pretty smart, thanks vnp. Mark your reply as answer and vote up.
• Lin Ma: @janos, I do not think there is extra O(n) (like I did in a map), the O(n) is space used for next and random pointers, which are not extra. If I read your thoughts wrong, please feel free to correct me.