/**
* Definition for Node.
* class Node {
* val: number
* next: Node | null
* random: Node | null
* constructor(val?: number, next?: Node, random?: Node) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* this.random = (random===undefined ? null : random)
* }
* }
*/
type OldNode = Node;
type NewNode = Node;
/**
*
* @complex T(n)/S(1)
* @param {(Node | null)} head
* @return {*} {(Node | null)}
*/
function copyRandomList(head: Node | null): Node | null {
let current: Node | null = head,
newHead: Node | null = null,
newLast: Node | null = null;
const map: Map<OldNode, NewNode> = new Map<OldNode, NewNode>();
while (current) {
const newNode: Node = new Node(current.val, null, null);
map.set(current, newNode);
!newHead && (newHead = newNode);
if (newLast) {
newLast = newLast.next = newNode;
} else {
newLast = newNode;
}
current = current.next;
}
current = head;
newLast = newHead;
while (current) {
newLast.random = map.get(current.random) || null;
newLast= newLast.next;
current = current.next;
}
return newHead;
};