Clear O(n) complexity with O(1) space in Python


  • 2
    X
    class Solution:
        # @param head, a RandomListNode
        # @return a RandomListNode
        def copyRandomList(self, head):
            if not head:return None
            self.copyNext(head)
            self.copyRandom(head)
            return splitList(head)
    
            
        def copyNext(self,head):
            while head:
                newNode = RandomListNode(head.label)
                newNode.random = head.random
                newNode.next = head.next
                head.next = newNode
                head = head.next.next
    
        def copyRandom(self,head):
            while head:
                if head.next.random:
                    head.next.random = head.random.next
                head = head.next.next 
    
        def splitList(self,head):
            newHead = head.next
            while head:
                tmp = head.next
                head.next = tmp.next
                head = head.next
                if tmp.next:
                    tmp.next = tmp.next.next
            return newHead

  • 0
    A

    @xiang19 could you please explain why "newNode.random = head.random" is needed?


Log in to reply
 

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