138. Copy List with Random Pointer - Medium

前往題目

想法

• 關鍵應該是random要怎麼接上，一個想法是先疊代整個list deepcopy出沒有random的list，過程中建立hashmap映射值和其對應的node，這樣時間上是O(2N)，但空間需要O(N)
• 只想得到用map儲存node和值的對應關係，但是值不是唯一所以不能當作key，有了node的時候值又是多餘的。可能可以用array，但是最大的array會需要$10^4$的空間
• 寫了快半小時，看解答

思路

和想法差不多，有兩個點我沒有思考到

• 第一次疊代應該要建立所有node就好，先不要連接
• 同時建立Map，它應該要映射舊node和新node

1. 第一次循環，建立新的nodes，先不連接，並儲存舊的node和新的node之間的映射
2. 第二次循環利用map把新的node的next以及random都連接起來

Code

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> oldToNew = new HashMap<>();
        oldToNew.put(null, null);

        Node curNode = head;

        // Build new nodes
        while (curNode != null) {
            // New node
            Node copy = new Node(curNode.val);
            oldToNew.put(curNode, copy);
            curNode = curNode.next;
        }

        // Reset
        curNode = head;
        
        while (curNode != null) {
            // Obtain new node
            Node copy = oldToNew.get(curNode);
            // Assign corresponding nodes
            copy.next = oldToNew.get(curNode.next);
            copy.random = oldToNew.get(curNode.random);
            curNode = curNode.next;
        }

        return oldToNew.get(head);
    }
}

// 寫到一半廢棄code
class Solution {
    public Node copyRandomList(Node head) {
        // Base case
        
        Node originHead = head;

        // Store val to nodes
        HashMap<Node, Integer> map = new HashMap<>();

        Node dummyHead = new node();
        Node newHead = new node();
        dummyHead.next = newHead;

        // Deepcopy the list
        for (head != null) {
            newHead.val = head.val;
            map.put()
            head = head.next; // Move pointer
            newHead.next = new Node();
            newHead = newHead.next; // Move pointer
        }
        
        // Attach null node
        newHead.next = null;





        return newHead;
    }
}