[JavaScript] 138. Copy List with Random Pointer, 해시맵 사용, 쉬운설명

138. Copy List with Random Pointer

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.

n의 길이를 하고있는, 링크리스트가있고, 각 노드는 노말 포인터와, 랜덤 포인터를 가지고있고 이 랜덤 포인터는 리스트에 포함된 아무 노드나 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.

deep copy 리스트를 만드세요. deep copy는 n 길이와 완전히 새로운 노드 들로 만들어져있어야하고, 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.

 

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]]

 

계획

문제 설명

 

짧게 요약하면, input과 같은 linkedList를 만들어 내야하는데, 그냥 LinkedList와 다른점은, random이라 불리는 포인터가 하나더 있는 것입니다. 

 

문제 해결 전략

 

해시맵을 사용하여 풀어보도록하겠습니다. 

 

우선 hashMap에 input으로 받은 root를 key값으로 써주고, value를 현재 root node의 val값을 가진 node를 넣어줍니다. 

 

 root.next를 반복하며 linkedlist끝에 도달할때까지 모든node를 map에 넣어줍니다. 

 

모두 넣어주면, 다시 root는 head위치로 돌려보내고 새로운 loop를 시작합니다. 

 

 

새로운 loop는 만들어진 hashmap을 이용하여, hashmap의 value 값이였던, Node(root.val)을 가져와서 그 값의 next와 랜덤 값을 가르켜 값을 지정해주면됩니다. 

 

그리고 root를 다음 root로 옮겨주며, 다시 LinkedList의 끝 노드까지 도달합니다. 

 

리턴은 map의 head값을 리턴해주면 완성됩니다.  

 

 

 

 

 

해설

 

/**
 * // 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
    
    let root = head
    let map = new Map()
    
    while(root){ // root와 노드를 map에 넣어주는 과정
        console.log(root)
        map.set(root, new Node(root.val)) 
        root = root.next 
        
    }
    
    root = head
    while(root){
        map.get(root).next = map.get(root.next) || null //맵에 val 값인 노드를 가져와서 그노드의 다음값을 map에 root의 다음값을 가져오게한다. 
        map.get(root).random = map.get(root.random) || null // root가 가진 random값을 맵에서 찾아 root.random에 지정
        root = root.next // 다음 root로 이동
    }
    
    return map.get(head)
};