138. 复制带随机指针的链表

• 注意random指针可能指向None的情况，此时读取和插入map中的操作要小心。

    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return head

        dummy = Node(-1,None,None)
        copycur = dummy
        cur = head
        copymap = {}
        while cur:
            if cur not in copymap.keys():
                node = Node(cur.val, None, None)
                copymap[cur] = node
            # 注意cur.random为空的时候不要插入到copymap中
            if cur.random and cur.random not in copymap:
                node = Node(cur.random.val, None, None)
                copymap[cur.random] = node
            copycur.next = copymap[cur]
            copycur = copycur.next
            # 注意cur.random为空的时候copymap中查不到对应的value
            if not cur.random:
                copycur.random = None
            else:
                copycur.random = copymap[cur.random]
                
            cur = cur.next

        return dummy.next

• 解法二，空间复杂度O(1)，遍历三次(第一轮所有Node复制一份在原Node的后面，第二轮random指针的指向，第三轮拆分链表)。

    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return head

        # 第一轮,copy所有node
        cur = head
        while cur:
            node = Node(cur.val, None, None)
            last = cur.next
            cur.next = node
            node.next = last
            cur = last

        # 第二轮,完成random指针
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            else:
                cur.next.random = None
            cur = cur.next.next

        # 第三轮,把链表拆开
        cur = head
        dummy = Node(-1, None, Node)
        curcopy = dummy
        while cur:
            curcopy.next = cur.next
            last = cur.next.next
            cur.next = last
            curcopy = curcopy.next
            curcopy.next = None
            cur = last
        return dummy.next