[Leetcode] 138. Copy List with Random Pointer - JS

https://leetcode.com/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 길이 n의 연결리스트에 각 노드에는 random 포인터를 포함한다.
- 깊은 복사본으로 정확히 n개의 새 노드로 구성되어야 한다.
- 복사된 새 노드의 포인터도 새 노드를 가리켜야한다.
- 복사된 연결 리스트의 head를 반환하라.
- 연결된 목록은 입력/출력에서 n개의 노드 목록으로 표시됩니다. 
- 각 노드는 [val, random_index] 쌍으로 표시됩니다.
- val: Node.val을 나타내는 정수
- random_index: 무작위 포인터가 가리키는 노드의 인덱스(0에서 n-1 범위), 또는 노드를 가리키지 않는 경우 null입니다.

제한조건
--------------------
- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- Node.random은 null 또는 어떤 Node의 위치이다.

 

2. 접근 방법

접근방법
--------------------
원본 노드의 참조값을 key로 가지는 Map 객체에 복사된 노드를 매핑한다.
이후 복사된 노드의 next, random 값을 지정해준다.

 

 

3. 코드

var copyRandomList = function(head) {
    if (head === null) return null;

    const nodeMap = new Map(); // 원본 노드 -> 복사된 노드 매핑

    let currentNode = head;
    while (currentNode !== null) {
        // 복사된 노드 생성 후 현재 노드와 매핑
        nodeMap.set(currentNode, new _Node(currentNode.val,null, null));
        currentNode = currentNode.next
    }

    currentNode = head;
    while (currentNode !== null) {
        const copiedNode = nodeMap.get(currentNode);
        copiedNode.next = currentNode.next !== null ? nodeMap.get(currentNode.next) : null;
        copiedNode.random = currentNode.random !== null ? nodeMap.get(currentNode.random) : null;
        currentNode = currentNode.next;
    }
    return nodeMap.get(head)
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

Node는 객체로 참조값을 참조하여 Node를 참조할 수 있다.

즉, 첫번째 순회 시 원본 Node 참조값에 대해 새로운 Node를 매핑해준다.

 

두번째 순회 시에는 원본 Node 참조값을 Map에서 참조하여 copiedNode에 접근한다.

copiedNode의 next, random 값을 지정해줘야하는데,

Map에서 참조한 원본 노드의 next, random Node들을 다시 Map에서 참조하여 각각 할당해준다.

 

객체의 참조값을 Map에 매핑하는 부분에서 깊이가 깊어지고 반복되는 부분이 있어서 헷갈렸다.

 

연결리스트 문제를 반복적으로 풀어보면서 Node라는 객체에 대해 정확히 이해하고 넘어가야겠다.