3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.