[leetcode #138] Copy List with Random Pointer

Problem

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.

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
・ -10⁴ <= Node.val <= 10⁴
・ Node.random is null or is pointing to some node in the linked list.

Idea

주어진 리스트를 deep copy하라는 문제다. 리스트를 구성하는 노드는 다음 노드를 가리키는 next 포인터 뿐 아니라 리스트를 구성하는 노드 중 아무거나 가리키는 random 포인터도 가지고 있다.

우선 주어진 리스트의 next 포인터를 움직이면서 각 노드를 생성한 뒤 연결한다. 이 때 random 포인터 생성을 위한 map을 준비하고, 기존 노드를 key로 새로운 노드를 value로 넣는다.

주어진 리스트를 다시 탐색하면서 새로운 노드의 random 포인터 값을 기존 노드의 random 포인터를 key로 한 value로 설정한다. 이렇게 하면 기존 리스트와 똑같은 형태로 random 포인터를 설정할 수 있다.

Time Complexity: O(n)
Space Complexity: O(n)

재귀함수를 이용하면 두 번 탐색하지 않아도 된다. 재귀함수에서 기존 노드의 복사를 끝내고 map에 기존 노드와 새로운 노드를 각각 key와 value로 넣는다. 재귀함수 호출 이후에 random 포인터를 설정하면 새로운 노드의 생성도 완료된 상태이므로 더 효율적으로 문제를 풀 수 있다.

Solution

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

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

        Map<Node, Node> map = new HashMap<>();
        Node res = new Node(head.val);
        Node cur = head;
        Node copied = res;

        while (cur != null) {
            copied.next = cur.next == null ? null : new Node(cur.next.val);
            map.put(cur, copied);
            cur = cur.next;
            copied = copied.next;
        }

        cur = head;
        copied = res;
        while (cur != null) {
            copied.random = map.getOrDefault(cur.random, null);
            cur = cur.next;
            copied = copied.next;
        }

        return res;
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

재귀함수를 이용해 푸는 법은 다음과 같다.

class Solution {

    Map<Node,Node> map = new HashMap<>();

    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node temp = new Node(head.val);
        map.put(head,temp);
        temp.next = copyRandomList(head.next);
        temp.random = map.get(head.random);
        return temp;
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

Reference

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