Java复杂链表的复制

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

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        //使cur指向原链表的头节点
        Node cur = head;
        //创建哈希表
        //<原链表节点, 新的链表节点>
        Map map = new HashMap<>();
        while(cur != null){
            //建立新的节点
            Node node = new Node(cur.val);
            //向哈希表中添加键值对(原cur节点, 新cur节点)
            map.put(cur, node);
            //更新cur, 继续往后遍历
            cur = cur.next;
        }
        //cur指向原链表的头节点
        cur = head;
        while(cur != null){
            //构建新链表的 next 和 random 指向
            //map.get(cur).next ==> node.next
            //map.get(cur.next) ==> 获取到cur.next对应的新节点
            map.get(cur).next = map.get(cur.next);
            //random同理
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //返回新链表的头节点
        return map.get(head);
    }
}