Two python solution: iteration and recursion. Both iterate the list once.


  • 0
    C

    Dfs is the first solution that comes to my mind. Because we can deal with list like a graph
    Dfs method can deal the situation with multiple random pointers exsit.
    To simply things, you can also use iteration.
    Both solutions are listed below.

    class Solution(object):
    def copyRandomList(self, head):
    """
    :type head: RandomListNode
    :rtype: RandomListNode
    """
    dic = {}
    if head == None:
    return None
    dic[head] = RandomListNode(head.label)
    node = head
    while node != None:
    if node.random != None:
    if node.random not in dic:
    dic[node.random] = RandomListNode(node.random.label)
    dic[node].random = dic[node.random]
    if node.next != None:
    if node.next not in dic:
    dic[node.next] = RandomListNode(node.next.label)
    dic[node].next = dic[node.next]
    node = node.next
    return dic[head]

    class Solution(object):
    def copyRandomList(self, head):
    """
    :type head: RandomListNode
    :rtype: RandomListNode
    """
    dic = {}
    if head == None:
    return None
    self.dfs(head, dic)
    return dic[head]

    def dfs(self, node, dic):
        newNode = RandomListNode(node.label)
        dic[node] = newNode
        if node.next != None:
            if node.next not in dic:
                self.dfs(node.next, dic)
            newNode.next = dic[node.next]
        if node.random != None:
            if node.random not in dic:
                self.dfs(node.random, dic)
            newNode.random = dic[node.random]

  • 0
    C
    class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: RandomListNode
            :rtype: RandomListNode
            """
            dic = {}
            if head == None:
                return None
            dic[head] = RandomListNode(head.label)
            node = head
            while node != None:
                if node.random != None:
                    if node.random not in dic:
                     dic[node.random] = RandomListNode(node.random.label)
                    dic[node].random = dic[node.random]
                if node.next != None:
                    if node.next not in dic:
                        dic[node.next] = RandomListNode(node.next.label)
                    dic[node].next = dic[node.next]
                node = node.next
            return dic[head]
    
    class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: RandomListNode
            :rtype: RandomListNode
            """
            dic = {}
            if head == None:
                return None
            self.dfs(head, dic)
            return dic[head]
          
        def dfs(self, node, dic):
            newNode = RandomListNode(node.label)
            dic[node] = newNode
            if node.next != None:
                if node.next not in dic:
                    self.dfs(node.next, dic)
                newNode.next = dic[node.next]
            if node.random != None:
                if node.random not in dic:
                    self.dfs(node.random, dic)
                newNode.random = dic[node.random]
    

Log in to reply
 

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