剑指offer35
剑指offer35：复制复杂链表
public Node copyRandomList(Node head) {
if(head==null){
return null;
}
HashMap<Node,Node> 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);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}
题解：通过哈希表，进行二次遍历
当第一次遍历时，将链表中的对象放入到map中生成副本
然后进行第二次遍历，将原先的对象的next指针域赋给副本的对象
将原先的对象的random域赋给副本的random域
这就完成了复杂连边的复制
时间复杂度：O（n）
空间复杂度：O（n）
投递微软等公司6个岗位 >