138. Copy List with Random Pointer

知道就是知道，不知道就是不知道

Key idea: insert copy of each node into original list

核心： 把每个点的副本插入原始的list

0, Original list

1, Copy "next" and "value" into the original list

2, Copy "random"

3, Split original list and copy list, return copy head

Solution:

1. copy next

2. copy random

3. split origin and copy

Don't modify original list when finish copy

Be careful with the case of current.random == null

Java(very efficient)

别忘了最后将orignial list指针next还原

class Solution {
    public Node copyRandomList(Node head) {
        Node dump = new Node(0);
        dump.next = head;
        if(head == null) return null;
        
        // insert new node, copy next
        Node curr = head;
        while(curr != null) {
            Node insert = new Node(curr.val);
            insert.next = curr.next;
            curr.next = insert;
            curr = curr.next.next;
        }
        
        // deep copy random
        curr = head;
        while(curr != null) {
            if(curr.random == null)
                curr.next.random = null;
            else
                curr.next.random = curr.random.next;
            curr = curr.next.next;
        }
        
        // remove original node
        curr = head.next;
        dump.next = curr;
        while(curr.next != null) {
            head.next = head.next.next;
            curr.next = curr.next.next;
            head = head.next;
            curr = curr.next;
        }
        // add tail
        head.next = null;
        curr.next = null;
        
        return dump.next;
    }
}

Python

在split步骤时，在head指针挪动时，每次应该只移动一步head = head.next，因上面一步已经将head.next指向了head.next.next.