首页 > itarticle > 138. copy list with random pointer 解法

138. copy list with random pointer 解法

admin 11月 12, 2020 0

138. Copy List with Random Pointer

Difficulty: Medium

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a of the list.

Example 1:

1
2
3
4
5
6
 
Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

  1. You must return the copy of the given head as a reference to the cloned list.

解法

  此题和clone graph那道题一样用BFS/DFS+hashmap求解;

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
from collections import deque
class :
    def copyRandomList(self, head: 'Node') -> 'Node':
        dic = {}
        def DFS(head):
            if not head:
                return None
            if head in dic:
                return dic[head]                
            new = Node(head.val, None, None)
            dic[head] = new
            new.next = DFS(head.next)
            new.random = DFS(head.random)
            return new
        return DFS(head)

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 

from collections import deque
class :
    def copyRandomList(self, head: 'Node') -> 'Node':
        dic = {}
        if not head: 
            return None
        q = deque([head])
        new = Node(head.val, None, None)
        dic[head] = new
        while q:
            node = q.popleft()
            if node.next:
                if node.next not in dic:                    
                    dic[node.next] = Node(node.next.val, None, None)
                    q.append(node.next)
                dic[node].next = dic[node.next]
            if node.random:
                if node.random not in dic:
                    dic[node.random] = Node(node.random.val, None, None)
                    q.append(node.random)
                dic[node].random = dic[node.random]
        return dic[head]
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能