Python Solution without extra space cost


  • 0
    D

    The idea is to create the link between origin and its copy and delete the link at last.

    class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: RandomListNode
            :rtype: RandomListNode
            """
            p = head
            copy_head = RandomListNode(0)
            copy_p = copy_head
            while p:
                copy = RandomListNode(p.label)
                copy.ori = p
                p.copy = copy
                copy_p.next = copy
                copy_p = copy_p.next
                p = p.next
            copy_head = copy_head.next
            copy_p = copy_head
            while copy_p:
                if copy_p.ori.random != None:
                    copy_p.random = copy_p.ori.random.copy
                copy_p = copy_p.next
            copy_p = copy_head
            while copy_p:
                del copy_p.ori
                copy_p = copy_p.next
    
            p = head
            while p:
                del p.copy
                p = p.next
    
            return copy_head
    

Log in to reply
 

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