Regular solution in Python, using hashtable


  • 0
    X
    class Solution:
        # @param head, a RandomListNode
        # @return a RandomListNode
        def copyRandomList(self, head):
            if head is None: return None
            table = {}
            copyhead = RandomListNode(head.label)
            table[head] = copyhead
            ptr = head
            copyptr = copyhead
            while ptr.next != None:   #need to access ptr.next.label later, check if ptr.next is None is necessary
                copynext = RandomListNode(ptr.next.label)
                table[ptr.next] = copynext
                copyptr.next = copynext
                ptr = ptr.next
                copyptr = copyptr.next
            ptr = head
            while ptr != None:
                if ptr.random is not None:  #if ptr.random is None, will raise keyError, None can't be key of dict
                    table[ptr].random = table[ptr.random]
                ptr = ptr.next
            return copyhead
    

    Naive method: O(N)time O(N)space
    go through the whole linked list once. create all the nodes. store them in a hashtable, using the original node as index
    go through the whole linked list again, copy the randome pointers
    Not a very clever solution, but it works.


  • 0

    haha,I have the same idea.
    here is my code

    class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        if not head: return None
        newHead=RandomListNode(head.label)
        np ,p = newHead,head
        dic={}
        dic[head]=newHead
        while p.next:
            p = p.next
            q = RandomListNode(p.label)
            np.next ,np,dic[p] = q,q,q
        np ,p = newHead,head
        while p:
            if p.random in dic:
                np.random = dic[p.random]
            p , np = p.next,np.next
        return newHead

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.