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

用哈希表建立索引

题目链接-来源：力扣（LeetCode）

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

思路：

原链表的每个 random 指针指向了一个随机节点的引用，对于我们新建的复制链表而言，这个引用的意义不大，关键是要找出这个节点对应的「序号」，我们才能在复制的链表当中按图索骥，建立一个相同的链接。
给链表节点「标号」可以用哈希表完成，我们遍历原链表，对每个节点维护一个 <Node, Integer> 的映射，这个 Integer 就是节点的编号。同时遍历得到的节点值，我们拿来复制新的链表节点，记得用一个能快速索引的数据结构（可以用另一个哈希表，或者直接用一个节点数组ArrayList）帮助我们存储这些复制的节点，方便后续索引。
然后我们再次遍历原链表，这一次我们只关心 random 指针，在哈希表中我们可以获得这个 random 节点的序号，那么我们将当前的复制链表节点的 random 指针指向其相同序号对应的节点即可。

时间复杂度：O(n)
空间复杂度：O(n)

实现：

class Solution {
    public Node copyRandomList(Node head) {
        Node prehead = new Node(0);
        Node cur = prehead;
        Node preCopy = new Node(0);
        Node curCopy = preCopy;
        prehead.next = head;
        Map<Node, Integer> map = new HashMap<>();
        ArrayList<Node> copy = new ArrayList<>();
        int i = 0;
        while (cur.next != null) {
            Node next = cur.next;
            map.put(next, i++);
            
            Node nextCopy = new Node(next.val);
            curCopy.next = nextCopy;
            copy.add(nextCopy);
            
            cur = next;
            curCopy = nextCopy;
        }
        cur = prehead;
        curCopy = preCopy;
        while (cur.next != null) {
            Node next = cur.next, nextCopy = curCopy.next;
            if (next.random != null) {
                nextCopy.random = copy.get(map.get(next.random));    
            }
            
            cur = next;
            curCopy = nextCopy;
        }
        return preCopy.next;
    }
}