Copy List with Random Pointer

[huimeich]

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.

Example 1:

Input: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation: Node 1's value is 1, both of its next and random pointer points to Node 2. Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

You must return the copy of the given head as a reference to the cloned list.

[huimeich]

def copyRandomList(self, head: 'Node') -> 'Node':
    if head is None: return None
    ptr = head
    while ptr:
        newnode = Node(ptr.val, None, None)
        newnode.next = ptr.next
        ptr.next = newnode
        ptr = newnode.next
    ptr = head
    while ptr:
        ptr.next.random = ptr.random.next if ptr.random else None
        ptr = ptr.next.next
    ptr = head
    curr = head.next
    while ptr:
        newnode = ptr.next
        ptr.next = ptr.next.next
        ptr = ptr.next
        newnode.next = ptr.next if ptr else None
    return curr