力扣热门100题之随机链表的复制

核心思路第一遍遍历把每个旧节点复制一份用Map旧节点, 新节点存起来第二遍遍历给每个新节点设置next和randomnewNode.next map.get(oldNode.next)newNode.random map.get(oldNode.random)返回复制链表的头完整代码实现/* // 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) { if(head null) return null; // 映射旧节点 - 新节点 MapNode, Node map new HashMap(); Node cur head; // 1. 先复制所有节点只赋值 val while(cur ! null){ map.put(cur, new Node(cur.val)); cur cur.next; } // 在设置next random cur head; while(cur ! null){ Node newNode map.get(cur); newNode.next map.get(cur.next); newNode.random map.get(cur.random); cur cur.next; } // 返回复制出的头节点 return map.get(head); } }