剑指offer_02剑指Offer35复杂链表的复制

剑指 Offer 35. 复杂链表的复制

坚持就是胜利

思路：
1.将所有结点作为key存入哈希表中（方便找到）
2.遍历原链表，得到它的next和random，得到这两个Node值，在哈希表中找到这两个key对应的value，将当前结点指向这两个value，相当于深拷贝；

/**
 * 哈希表做法
 * 相当于深拷贝
 */
public class _02剑指Offer35复杂链表的复制 {

    // 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) {
            Node ans =head;
            HashMap<Node, Node> map = new HashMap<>();

            while (ans != null) {
                map.put(ans, new Node(ans.val));
                ans = ans.next;
            }

            ans = head;
            while (ans != null){
                //将原链表中对应的结点目标拷贝给哈希表中的新结点，让它成为新的链表
                map.get(ans).next = map.get(ans.next);
                map.get(ans).random = map.get(ans.random);
                ans = ans.next;
            }

            //最后返回的是哈希表中对应的头节点
            return map.get(head);

        }
    }
}