Description: 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. 所以新的Node包含三个值，val, next, random, 其中，next 和 random 的值是Node, val是int值.
Link: https://leetcode.com/problems/copy-list-with-random-pointer/
思路: 首先最重要的是一定要理解deep copy, 就是要重新生成一个链表，复制所有的节点和节点之间的关系，节点一定要一个一个重新生成，而不是使用原链表的节点。因为如果是使用原链表的节点，这个题目就没有必要出现了，我刚开始就很纠结，感觉这是个啥？然后我们先不考虑random.
rhead = Node(0) r = rhead p = head while p: node = Node(p.val) r.next = node r = r.next p = p.next return rhead.next
我们考虑random，问题就在于，我们不知道原节点的random到底指向了哪个节点？我们就想，那我们把原链表每个节点的random都记下来不就好了，但问题是我们记下来的是原链表上的节点，我们仍然不知道对应新链表上的哪个节点，所以新旧链表之间需要关联。负雪明烛博客中的方法特别精巧，建立每个对应节点的关联，一一对应。这样我们找到旧节点的random node, 就可以dict中的一一对应找到新节点。
""" # Definition for a Node. class Node: def __init__(self, x, next=None, random=None): self.val = int(x) self.next = next self.random = random """ class Solution(object): def copyRandomList(self, head): """ :type head: Node :rtype: Node """ rhead = Node(0) r = rhead p = head nodeDict = dict() while p: node = Node(p.val) r.next = node r = r.next nodeDict[p] = r p = p.next p = head while p: if p.random: nodeDict[p].random = nodeDict[p.random] p = p.next return rhead.next
日期: 2020-11-26 连续四天都没有做题，真的很愧疚，加油呀！