mycode
报错：Node with val 1 was not copied but a reference to the original one.
其实我并没有弄懂对于ListNode而言咋样才叫做深拷贝了
""" # Definition for a Node. class Node(object): def __init__(self, val, next, random): self.val = val self.next = next self.random = random """ class Solution(object): def copyRandomList(self, head): """ :type head: Node :rtype: Node """ if not head : return None dummy = p = ListNode(-1) while head: p.next = head p = p.next head = head.next return dummy.next
这道链表的深度拷贝题的难点就在于如何处理随机指针的问题，由于每一个节点都有一个随机指针，这个指针可以为空，也可以指向链表的任意一个节点，如果我们在每生成一个新节点给其随机指针赋值时，都要去遍历原链表的话，OJ 上肯定会超时，所以我们可以考虑用 HashMap 来缩短查找时间，第一遍遍历生成所有新节点时同时建立一个原节点和新节点的 HashMap，第二遍给随机指针赋值时，查找时间是常数级。
参考
https://www.cnblogs.com/zuoyuan/p/3745126.html
1、先不考虑random的问题，在原链表上构建copy
2、在copy链表上，利用now.next.random 也需要等于now.random.next实现随即指针的拷贝
3、两个链表分离
""" # Definition for a Node. class Node(object): def __init__(self, val, next, random): self.val = val self.next = next self.random = random """ class Solution(object): def copyRandomList(self, head): """ :type head: Node :rtype: Node """ if head == None: return None tmp = head while tmp: newNode = Node(tmp.val,None,None) newNode.next = tmp.next tmp.next = newNode tmp = tmp.next.next tmp = head while tmp: if tmp.random: tmp.next.random = tmp.random.next tmp = tmp.next.next newhead = head.next pold = head pnew = newhead while pnew.next: pold.next = pnew.next pold = pold.next pnew.next = pold.next pnew = pnew.next pold.next = None pnew.next = None return newhead
leetcode-hard-ListNode-Copy List with Random Pointer-NO
原文：https://www.cnblogs.com/rosyYY/p/11050372.html