LC 138随机链表的复制Copy List with Random Pointer　中等

深拷贝一条带 next 与 random 指针的链表，返回全新副本的头节点。

思路 迭代三步：原位克隆插入、按 random 同步复制、奇偶拆链。时间 O(n)，空间 O(1)。

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next, None)
            cur = cur.next.next
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        old, new = head, head.next
        dummy = new
        while old:
            old.next = new.next
            old = old.next
            if old:
                new.next = old.next
                new = new.next
        return dummy