[LeetCode] 138. Copy List with Random Pointer, Medium

1. 문제

• next와 random 필드를 가지는 노드로 구성된 단일 연결 리스트를 깊은 복사를 통해 새로운 노드로 구성된 리스트를 반환하라.
• 새로운 리스트는 기존 노드를 참조해서는 안되고, 기존 리스트 역시 변경되면 안된다.

/**
 * 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 {
    let p1 = head;

    // 1. 기존 노드 복사본 뒤에 붙이기.
    while(p1) {
        const newNode = new _Node(p1.val);
        newNode.next = p1.next;
        p1.next = newNode;
        p1 = newNode.next;
    }
    
    // 2. 기존 노드 random 값을 이용해 새로운 노드 random 갱신.
    p1 = head;
    while(p1) {
        if(p1.random) {
            p1.next.random = p1.random.next;
        }
        p1 = p1.next.next;
    }

    const dummy = new _Node(0);
    let dummyP = dummy;

    // 3. 기존 리스트와 분리.
    p1 = head;
    while(p1) {
        dummyP.next = p1.next;
        dummyP = dummyP.next;
        p1.next = p1.next.next;
        p1 = p1.next;
    }

    return dummy.next;
};

• 못풀어서 다른 사람 풀이를 참고했다. 기존 노드의 바로 뒤에 새로운 노드를 붙이고, random을 갱신해 분리하는 식으로 풀이한다.
• 별도 리스트로 구성해가면서 풀어보려고 했는데, random 필드 때문에 막혔다.