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.