[Medium] 138. Copy List with Random Pointer

문제

https://leetcode.com/problems/copy-list-with-random-pointer/

 

Copy List with Random Pointer - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

 

length n의 링크된 목록은 각 노드가 목록의 임의의 노드를 가리킬 수 있는 추가 랜덤 포인터를 포함하도록 주어집니다.
목록의 기본 복사본을 구성합니다. 딥 복사본은 정확히 n개의 새 노드로 구성되어야 하며, 각 새 노드는 해당 원래 노드의 값으로 값을 설정합니다. 새 노드의 다음 및 임의 포인터는 원래 목록과 복사된 목록의 포인터가 동일한 목록 상태를 나타내도록 복사된 목록의 새 노드를 가리켜야 합니다. 새 목록의 포인터는 원래 목록의 노드를 가리키지 않아야 합니다.
예를 들어, 원본 목록에 두 개의 노드 X와 Y가 있는 경우, 여기서 X.random --> Y는 복사된 목록의 해당 두 노드 x와 y에 대해 x.random --> y입니다.
복사된 연결 목록의 head을 반환합니다.
연결된 목록은 입력/출력에 n개 노드의 목록으로 표시됩니다. 각 노드는 [val, random_index]의 쌍으로 표현된다.
val: Node.val을 나타내는 정수
random_index: 랜덤 포인터가 가리키는 노드의 인덱스(0 ~ n-1 범위) 또는 노드를 가리키지 않는 경우에는 null입니다.
코드에는 원래 링크된 목록의 head만 부여됩니다.

 

예시

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

 

제약 조건

Constraints:

  • 0 <= n <= 1000
  • -104 <= Node.val <= 104
  • Node.random is null or is pointing to some node in the linked list.

 

해결 코드

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    if(!head) {
      return null;
    }
    
    const brandNew = new Map();
    let n = head;
    
    while(n) {
      brandNew.set(n, new Node(n.val));
      n = n.next
    }
    
    n = head;
    
    while(n) {
      brandNew.get(n).next = brandNew.get(n.next) || null;
      brandNew.get(n).random = brandNew.get(n.random) || null;
      n = n.next;
    }
    
    return brandNew.get(head);
};

 

'leetCode' 카테고리의 다른 글

[Easy] 860. Lemonade Change  (0) 2022.07.26
[Medium] 2. Add Two Numbers  (0) 2022.07.19
[Medium] 143. Reorder List  (0) 2022.07.19
[Medium] 304. Range Sum Query 2D - Immutable  (0) 2022.07.15
[Medium] 910. Smallest Range II  (0) 2022.07.15