2022-10-14

[Zheaoli]

2022-10-14

[Dapeus]

[gongpeione]

/*
 * @lc app=leetcode id=138 lang=typescript
 *
 * [138] Copy List with Random Pointer
 */

// @lc code=start
/**
 * 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)
 *     }
 * }
 */

function copyRandomList(head: Node | null): Node | null {
    const nodeMap = new Map<Node, Node>();

    let headPointer = head;

    // copy node and store it to a map
    while (headPointer) {
        const copy = new Node(headPointer.val, null, null);
        nodeMap.set(headPointer, copy);
        headPointer = headPointer.next;
    }

    headPointer = head;
    while(headPointer) {
        const copy = nodeMap.get(headPointer);
        const next = nodeMap.get(headPointer.next) || null;
        const random = nodeMap.get(headPointer.random) || null;

        copy.next = next;
        copy.random = random;

        headPointer = headPointer.next;
    }

    return nodeMap.get(head) || null;
};
// @lc code=end

---

微信id: 弘树 来自 vscode 插件