Clear and short python O(2n) and O(n) solution


  • 22
    T
    class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        dic = dict()
        m = n = head
        while m:
            dic[m] = RandomListNode(m.label)
            m = m.next
        while n:
            dic[n].next = dic.get(n.next)
            dic[n].random = dic.get(n.random)
            n = n.next
        return dic.get(head)
    

    O(n)

    class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        dic = collections.defaultdict(lambda: RandomListNode(0))
        dic[None] = None
        n = head
        while n:
            dic[n].label = n.label
            dic[n].next = dic[n.next]
            dic[n].random = dic[n.random]
            n = n.next
        return dic[head]

  • 0
    Z

    Could you please add more explanation and examples? Thanks so much!


  • 0
    I

    What about this case: (the means the random pointer)

    A->B->C->D
    └->E->F
       └->G
    

    Your solution didn't deal the List of random pointer. Maybe it is
    uncorrect. I think your code will run out as:

    A->B->C->D
    └->E
    

    Sorry, I didn't see the sentence "which could point to any node in the list or null".
    It's my fault...


  • 1

    That second solution... brilliant. I'd just change dic to copy (and maybe n to node (and of course I'd indent the whole thing properly :-P)).


  • 0
    P

    Why wouldn't the new list's random point to an old list node?


  • 1
    F
    class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: RandomListNode
            :rtype: RandomListNode
            """
            dic = collections.defaultdict(lambda: RandomListNode(10))
            #dic[None] = None
            if head==None:
                return head
            n = head
            while n:
                dic[n].label = n.label
                if n.next==None:
                    dic[n].next=None
                else:
                    dic[n].next = dic[n.next]
                if n.random==None:
                    dic[n].random=None
                else:
                    dic[n].random = dic[n.random]
                n = n.next
            return dic[head]
    

    At the beginning, i do not understand why there shoule be" dic[None] = None",when i try several times, i have the above code Accepted , i hope this will help someone else confused about it.


  • 0
    S

    First soln uses get to cover None input is good!
    But can anyone gives me some hint as for why we need to copy label from entire RandomListNode(m.label) rather than node itself such as:

    dic[m] = m
    

    sorry as this question looks noob


  • 0
    E

    @StefanPochmann I think the reason he/she used dic is to be able to say return dic[head] (read return dickhead) which I think is pretty funny. Not sure I would do this in an interview though.


Log in to reply
 

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