[Leetcode][python]Copy List with Random Pointer/复制带随机指针的链表

淡淡的烟草味﹌ 2022-06-05 07:06 118阅读 0赞

## 题目大意 ##

一个链表中的每一个节点都有一个额外的随机指针，指向链表中的任意节点或空节点。对这个链表进行深拷贝。（要拷贝随即指针）

## 解题思路 ##

有两种思路，参考：  
[http://bookshadow.com/weblog/2015/07/31/leetcode-copy-list-random-pointer/][http_bookshadow.com_weblog_2015_07_31_leetcode-copy-list-random-pointer]  
[https://shenjie1993.gitbooks.io/leetcode-python/138%20Copy%20List%20with%20Random%20Pointer.html][https_shenjie1993.gitbooks.io_leetcode-python_138_20Copy_20List_20with_20Random_20Pointer.html]  
这里只写一种思路：链表的拷贝其实可以看做两个步骤，一个是节点数据的拷贝，另一个是节点关系的拷贝。我们也可以先把所有的节点进行拷贝，并存入字典中。然后遍历链表并拷贝两个指针。因为任意指针可能指向空指针，所以在字典中添加一个空指针项。

## 代码 ##

class Solution(object):
        def copyRandomList(self, head):
            """
            :type head: RandomListNode
            :rtype: RandomListNode
            """
            if not head:
                return None
            visited = dict()
            # 复制值
            node = head
            while node:
                visited[node] = RandomListNode(node.label)
                node = node.next
    
            # 给一个空值
            visited[None] = None
    
            # 复制关系
            node = head
            while node:
                visited[node].next = visited[node.next]
                visited[node].random = visited[node.random]
                node = node.next
            return visited[head]

## 总结 ##

[http_bookshadow.com_weblog_2015_07_31_leetcode-copy-list-random-pointer]: http://bookshadow.com/weblog/2015/07/31/leetcode-copy-list-random-pointer/
[https_shenjie1993.gitbooks.io_leetcode-python_138_20Copy_20List_20with_20Random_20Pointer.html]: https://shenjie1993.gitbooks.io/leetcode-python/138%20Copy%20List%20with%20Random%20Pointer.html