Python 1 pass solution


  • 1
    class Solution(object):
        def copyRandomList(self, head):
            if head == None: return None
            copyHead = RandomListNode(head.label)
            tmp = head
            t = copyHead
            m = {head: copyHead}
            while tmp:
                if tmp.next:
                    if tmp.next in m:
                        t.next = m[tmp.next]
                    else:
                        t.next = RandomListNode(tmp.next.label)
                        m[tmp.next] = t.next
                if tmp.random:
                    if tmp.random in m:
                        t.random = m[tmp.random]
                    else:
                        t.random = RandomListNode(tmp.random.label)
                        m[tmp.random] = t.random
                t = t.next
                tmp = tmp.next
            return copyHead
    

  • 0

    Could be shorter.

    class Solution(object):
        def copyRandomList(self, head):
            d = {}
            p = head
            chead = dummy = RandomListNode(-1)
            while p:
                if p.label not in d:
                    d[p.label] = RandomListNode(p.label)
                dummy.next = d[p.label]
                if p.random:
                    if p.random.label not in d:
                        d[p.random.label] = RandomListNode(p.random.label)
                    dummy.next.random = d[p.random.label]
                dummy = dummy.next
                p = p.next
            return chead.next
    

Log in to reply
 

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