[LeetCode] 138. Copy List with Random Pointer

😎풀이

해시 맵 자료구조를 사용해 풀이하기 좋은 문제이다.

풀이 과정의 중요 절차는 다음과 같다.

1. key를 현재 노드로 갖고, value를 복사된 노드로 갖는 해시 맵 생성
2. 현재 노드와 복사된 노드를 추적하며 next와 random에 해당하는 클론 노드를 연결
3. 해시 맵에 저장된 클론 head 반환

/**
 * 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 {
    if(!head) return null

    // 해시맵
    const hashMap = new Map<_Node, _Node>()
    let cur = head
    // 맵 초기화
    while(cur) {
        hashMap.set(cur, new _Node(cur.val))
        cur = cur.next
    }
    cur = head
    // random, next 연동
    while(cur) {
        const copiedNode = hashMap.get(cur)
        copiedNode.next = cur.next ? hashMap.get(cur.next) : null
        copiedNode.random = cur.random ? hashMap.get(cur.random) : null
        cur = cur.next
    }

    return hashMap.get(head)
};