A nice and easy Python DFS solution with explanation


  • 0
    P

    The first question to ask is : what will it actually is when a linked-list is with random pointer? The answer is a graph! So just follow the way one uses to deal with a graph, i.e. DFS or BFS whatever you like.

    DFS

    class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: RandomListNode
            :rtype: RandomListNode
            """
            # Use DFS at first
            self.visited = collections.defaultdict(RandomListNode)
            return self.DFS(head)
            
        def DFS(self, head):
            if not head:
                return None
            if head not in self.visited:
                newHead = RandomListNode(head.label) # newHead
                self.visited[head] = newHead
                newHead.next = self.DFS(head.next) # visit next branch
                newHead.random = self.DFS(head.random) # visite random branch
                return newHead
            else:
                return self.visited[head] # o/w return the refered as newHead
    

    BFS

    class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: RandomListNode
            :rtype: RandomListNode
            """
            # Try BFS this time
            # assume all node in queue have been copied before putting into the queue
            if not head: return None
            newHead = RandomListNode(head.label)
            visited = {head:newHead}
            queue = collections.deque([head])
            nextQ = collections.deque([])
            while queue:
                node = queue.popleft()
                newNode = visited[node] # creat new Node
                # next branch
                if node.next and node.next not in visited:
                    newNext = RandomListNode(node.next.label)
                    visited[node.next] = newNext
                    newNode.next = newNext
                    nextQ.append(node.next)
                elif node.next: # check not None
                    newNode.next = visited[node.next] # connect copy
                # random branch
                if node.random and node.random not in visited:
                    newRan = RandomListNode(node.random.label)
                    visited[node.random] = newRan
                    newNode.random = newRan
                    nextQ.append(node.random)
                elif node.random: # check not None
                    newNode.random = visited[node.random] 
                if not queue:
                    queue, nextQ = nextQ, queue # swap
            return newHead

Log in to reply
 

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