# 0138. Copy List with Random Pointer
###### tags: `Leetcode` `FaceBook` `Medium` `Linked List` `Deep Copy`
Link: https://leetcode.com/problems/copy-list-with-random-pointer/
## 思路
### 思路一 DFS
递归+HashMap
一定要先加进map，再递归
### 思路二 BFS
### 思路三
很Tricky的方法 直接在原地做
如果想不起来可以去看中文官方解答~
## Code
### 思路一

class Solution {
    Map<Node, Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        if(!map.containsKey(head)){
            Node newHead = new Node(head.val);
            map.put(head,newHead);
            newHead.next = copyRandomList(head.next);
            newHead.random = copyRandomList(head.random);
        }
        return map.get(head);
    }
}

### 思路二

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Queue<Node> q = new LinkedList<>();
        Node newHead = new Node(head.val);
        map.put(head,newHead);
        q.add(head);
        while(!q.isEmpty()){
            Node curr = q.poll();
            if(curr.next!=null && !map.containsKey(curr.next)){
                map.put(curr.next, new Node(curr.next.val));
                q.add(curr.next);
            }
            map.get(curr).next=curr.next==null?null:map.get(curr.next);
            if(curr.random!=null && !map.containsKey(curr.random)){
                map.put(curr.random, new Node(curr.random.val));
                q.add(curr.random);
            }
            map.get(curr).random=curr.random==null?null:map.get(curr.random);
        }
        return newHead;
    }
}

### 思路三

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        for(Node node = head; node != null; node = node.next.next){
            Node newNode = new Node(node.val);
            newNode.next = node.next;
            node.next = newNode;
        }
        for(Node node = head; node != null; node = node.next.next){
            if(node.random!=null){
                node.next.random = node.random.next;
            }
            else{
                node.next.random = null;
            }
        }
        Node newHead = head.next;
        for(Node node = head; node != null; node = node.next){
            Node nodeNew = node.next;
            node.next = node.next.next;
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }
        
        
        return newHead;
    }
}