# 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

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
randomMap[node.nodeID] = preNode
# setup regular part
while node.nextNode:
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

if __name__ == "__main__":

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


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.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.

• This method is pretty smart, thanks vnp. Mark your reply as answer and vote up. – Lin Ma Oct 12 '16 at 6:14
• @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. – Lin Ma Oct 17 '16 at 5:06