Sunday, May 18, 2014

Leetcode (Python): Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.

Solution

# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        return self.copyRandomListRec(head, {})
        
    def copyRandomListRec(self, head, used):
        if head == None:
            return None
        if head in used:
            return used[head]
        node = RandomListNode(head.label)
        used[head] = node
        node.next = self.copyRandomListRec(head.next, used)
        node.random = self.copyRandomListRec(head.random, used)
        return node

No comments :

Post a Comment