[leetcode 138] Copy List with Random Pointer

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

Return a deep copy of the 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) where random pointer points to, or null if it does not point to any node.

주어진 리스트를 copy하라.

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

Example 4:

Input: head = [] Output: [] Explanation: Given linked list is empty (null pointer), so return null.

 

문제 풀이:

- 새로 만든 리스트에 복사하지 않고 기존 리스트 포인터를 건드려서 계속 에러가 났다.

- 포인터 공부 다시해야 할 것 같다.

- 문제의 핵심은 기존 리스트에서 random에 해당하는 노드의 index를 찾는 것. 새로 복사한 리스트에 찾은 index만큼 이동하여 random 포인터를 연결해준다.

 

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        
        Node* copyList = new Node(0);
        Node* cur = copyList;
        
        Node*tmp = head;
        
        while(tmp){
            cur ->next = new Node(tmp->val);
            cur = cur->next;
            tmp = tmp->next;
        }
        
        tmp = head;
        cur = copyList;
        
       while(tmp){
           Node* rnode = tmp->random;
           cur = cur->next;
            
           if(rnode){
            
               int idx = 0;
               Node* orHead = head;
               
               while(rnode != orHead){
                   orHead = orHead ->next;
                   idx++;
               }
               
               Node* copyHead = copyList->next;

               while(idx>0){
                   copyHead = copyHead->next;
                   idx--;
                }
                
                cur->random = copyHead;
            }else {
               cur->random = NULL;
           }
           
            tmp = tmp->next;
            
        }
        return copyList->next;
    }
};