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

  分析：本题的难点主要就在于：random如何指向一个新的结点。 刚开始的想法就是遍历链表，然后每次生成一个新结点，把对应的属性赋值，然后问题就出现了：我们会发现，random对应的是一个指针，我们如果简单的使用 a.random = b.random 去给新结点进行赋值，就会出现多个指针指向同一个结点的情况。为了避免多个指针指向同一个结点，我们需要新链表的random指针指向一个新结点。

 　  为什么遍历的时候不每次生成一个新的结点：因为这里面有random指针，我们赋值next域的时候可以生成一个新结点，把旧链表对应的next信息输入进去，但是我们不能生成一个结点去表示random对应的结点，因为random对应的结点也在链表中，它的next域和random域该怎么处理？因此不能用生成新结点法。

　　为什么会用到哈希表：因为我们需要旧链表和新链表的结点进行对应，也就是 HashMap，每个旧结点都对应着一个新结点。

class Solution {
    public Node copyRandomList(Node head) {
        //哈希表
        if(head==null){
            return null;
        }
        HashMap map = new HashMap<>(); //旧结点和新结点产生映射关系
        Node cur = head;
        while(cur!=null){
            map.put(cur,new Node(cur.val)); //旧链表的每个结点都对应一个新结点，同时我们还生成了新结点（值域相同）
            cur = cur.next;
        }
        cur = head; 
        while(cur!=null){
            map.get(cur).next = map.get(cur.next); //cur对应的新结点的next指向cur.next对应的新结点
            map.get(cur).random = map.get(cur.random);//cur对应的新结点的random指向cur.random对应的新结点
            cur = cur.next;
        }
        return map.get(head); //返回新链表的头结点
    }
}

 　　cur 一直是指向旧链表的结点的，我们可以通过 get函数来获取到它对应的新链表结点，然后再通过 get函数获取 cur.next 对应的新结点，然后对next域进行赋值。random域同理。