[LinkedList][Medium] 138. Copy List With Random Pointer

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

 

 

 

Q. list가 주어질 때, 이 list의 노드는 next와 random pointer를 가지고 있다. 

 이 list를 깊은 복사를 하고, 그 결과를 반환하라. 

 

Solution. 

 복잡해 보이지만 간단한 문제. 

 list를 그냥 복사하고, random에 대해 복사한 대상에 대해 같은 복사대상을 pointing하게 해 주면 된다. 

 

 문제는 복사대상을 찾는 과정인데, 

 어떤 최적화를 거친것을 문제가 원하는가, 아니면 모든 대상에 대해 그냥 O(N)탐색을 허용하는가 하는 것이다. 

 

 결과적으로 별 최적화 없이 해도 accpected 되었다. 

 

 

public class Solution {
    public Node CopyRandomList(Node head) 
    {
        if(head == null)
            return null;

        Node orgNode = head;
        Node newHead = null;
        Node prev = null;
        while(orgNode != null)
        {
            Node node = new Node(orgNode.val);
            if(newHead == null)
                newHead = node;
            if(prev != null) 
                prev.next = node;
            prev = node;
            orgNode = orgNode.next;
        }

        orgNode = head;
        Node now = newHead;
        while(orgNode != null)
        {
            // node.val은 키가 아니다. 따라서 정확한 index를 찾아야 한다.
            now.random = orgNode.random==null ? null : findNode(newHead, findIndex(head, orgNode.random));
            now = now.next;
            orgNode = orgNode.next;
        }
        return newHead;
    }

    // 대상 포인터를 찾아서 index를 돌려준다. 
    int findIndex(Node head, Node random)
    {
        Node node = head;
        int idx = 0;
        while(node != null)
        {
            if(node == random)
                return idx;
            ++idx;
            node = node.next;
        }
        return -1;
    }
    
    // 해당 index의 노드를 돌려준다.
    Node findNode(Node head, int index)
    {
        if(index < 0)   return null;
        int idx = 0;
        Node cur = head;
        while(cur != null)
        {
            if(idx == index)
                return cur;
            ++idx;
            cur = cur.next;
        }
        return null;
    }
}

 

Acceptable 한 결과.