Leetcode 138. Copy List with Random Pointer(python)

题目

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 deep copy of the list.The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:val: an integer representing Node.valrandom_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

解析

刚看到这道题目的时候理解错了，以为node.random是一个数字，主要是他这个例子的表述方法有点让人误导。然后这道题看Leetcode的官方解法一脸懵，不太懂为啥这个题目要这么麻烦，后面看到了一种不那么麻烦的解法，这边就暂时先用这种不那么麻烦的解法，等二刷再研究leetcode的官方解法吧

解法：利用hashtable

这种解法的关键思想是，由于每个node的random point可能会指向任何一个node，所以在一次顺序遍历list中很难直接将random point也做好。为了更加方便的寻找random pointer指向的节点，可以把原来的node作为key，copy后的node作为值的方式存入hashtable。具体做法如下：

• 首先第一次顺序遍历原链表，构造一个传统意义上只有next的链表，同时将原node和copy_node以键值对方式储存
• 再次遍历原链表，通过键值对索引，给copy_node的random pointer赋值

class Solution(object):def copyRandomList(self, head):""":type head: Node:rtype: Node"""nodeDict = dict()dummy = Node(0,None,None)newHead = dummytmp = headwhile tmp:newNode = Node(tmp.val,tmp.next,None)nodeDict[tmp] = newNodenewHead.next = newNodetmp = tmp.nextnewHead = newHead.nexttmp = headwhile tmp:if tmp.random:nodeDict[tmp].random = nodeDict[tmp.random]tmp = tmp.nextreturn dummy.next

时间复杂度：O(n)
空间复杂度：O(n)

Note: 这种方法也超过了%85的用户，看起来也不错啊，不知道官方解法为啥这么复杂，留到以后再研究吧

参考：https://blog.csdn.net/fuxuemingzhu/article/details/80787528

解法2：递归

class Solution:def __init__(self):self.visited = {
    }def copyRandomList(self, head: 'Node') -> 'Node':if not head:return Noneif head in self.visited:return self.visited[head]node = Node(head.val,None,None)self.visited[head] = nodenode.next = self.copyRandomList(head.next)node.random = self.copyRandomList(head.random)return node