https://leetcode.com/problems/copy-list-with-random-pointer/
链表的一些trick

个人解答

  1. class Solution:
  2.     def copyRandomList(self, head: 'Node') -> 'Node':
  3.         # duplicate each node, insert behind
  4.         p = head
  5.         while p:
  6.             nxt = p.next
  7.             p.next = Node(p.val, nxt)
  8.             p = nxt
  10.         # random pointer
  11.         p = head
  12.         while p and p.next:
  13.             curr = p.next
  14.             nxt = curr.next
  15.             curr.random = p.random.next if p.random else None
  16.             p = nxt
  18.         # next pointer
  19.         p = head
  20.         while p and p.next and p.next.next:
  21.             curr = p.next
  22.             nxt = curr.next
  23.             curr.next = nxt.next
  24.             p = nxt
  26.         return head.next if head else None

题目分析

最简单的思路，用hash table存
如果不想用额外的空间，就需要充分利用原先链表的特性。
比如，新加入的节点先放到原节点的后边，更新完random之后，再更新next。

其它解法

naive的hash table解法

  1. class Solution:
  2.     def copyRandomList(self, head: 'Node') -> 'Node':
  3.         nodeMap = {}
  5.         dummy = Node(0)
  6.         p = head
  7.         q = dummy
  8.         while p:
  9.             q.next = Node(p.val)
  10.             nodeMap[p] = q.next
  11.             p = p.next
  12.             q = q.next
  14.         p = head
  15.         q = dummy.next
  17.         while p:
  18.             q.random = nodeMap[p.random] if p.random else None
  19.             p = p.next
  20.             q = q.next
  22.         return dummy.next