138. Copy List with Random Pointer - LeetCode

from typing import Optional


# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Optional[Node]' = None, random: 'Optional[Node]' = None):
        self.val = int(x)
        self.next = next
        self.random = random


class Solution0:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        dummy = Node(0)
        h1, h2 = head, dummy
        m, i, l2 = {}, 0, []
        while h1:
            m[h1], h2.next = i, Node(h1.val)
            l2.append(h2.next)
            h1, h2, i = h1.next, h2.next, i + 1
        h1, h2 = head, dummy.next
        while h1:
            i = m.get(h1.random, None)
            # assert h2
            h2.random = None if i is None else l2[i]
            h1, h2 = h1.next, h2.next
        return dummy.next


class Solution1:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        h = head
        m = {}
        while h:
            m[h] = Node(h.val)
            h = h.next
        h = head
        while h:
            n = m[h]
            n.next, n.random = m.get(h.next, None), m.get(h.random, None)
            h = h.next
        return m.get(head, None)


class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        h1 = head
        while h1:
            node = Node(h1.val)
            # A -> B
            # A -> A' -> B -> B'
            h1.next, node.next = node, h1.next
            h1 = node.next
        h1 = head
        while h1:
            if h1.random:
                h1.next.random = h1.random.next
            h1 = h1.next.next
        new_head = head.next
        h1, h2 = head, head.next
        while h1:
            # A -> A' -> B -> B'
            # A -> B  +  A' -> B'
            h1.next = h1.next.next
            h2.next = h2.next.next if h2.next else None
            h1, h2 = h1.next, h2.next
        return new_head