A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.Construct a deep copy of the list. The deep copy should consist of exactly nbrand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.Return the head of the copied linked list.The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
from __future__ import annotationsclass Node: def __init__(self, x: int, next: Node | None = None, random: Node | None = None): self.val = int(x) self.next = next self.random = randomclass Solution: # Time: O(n) # Space: O(1) extra (interweaves clones into the original list) def copy_random_list(self, head: Node | None) -> Node | None: if head is None: return None # Phase 1: insert each clone right after its original node current: Node | None = head while current is not None: nxt = current.next clone = Node(current.val, nxt) current.next = clone current = nxt # Phase 2: wire each clone's random from its original's random current = head while current is not None: clone = current.next assert clone is not None if current.random is not None: rand_clone = current.random.next assert rand_clone is not None clone.random = rand_clone current = clone.next # Phase 3: detach clones, restore the original, return the copy head current = head copy_head = head.next while current is not None: clone = current.next assert clone is not None current.next = clone.next tail = clone.next clone.next = tail.next if tail is not None else None current = current.next return copy_head
