剑指-复杂链表的复制-深拷贝HashMap

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

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

输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。

思路

1.创建HashMap 2.复制结点值 3.复制指向（next,random）

代码

/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */ import java.util.HashMap; public class Solution { public RandomListNode Clone(RandomListNode pHead) { HashMap<RandomListNode,RandomListNode> map = new HashMap<>(); RandomListNode cur = pHead; while(cur!=null){ map.put(cur, new RandomListNode(cur.label)); cur = cur.next; } cur = pHead; 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(pHead); } }

JAVA中的拷贝

对象拷贝

“=”对于基本数据类型是 值传递； “=”对于对象是 引用传递。

浅拷贝

基本数据类型，属性值修改不相互影响； 引用类型，内存地址赋值，会相互影响。

深拷贝

基本数据类型，同浅拷贝，不影响。 引用类型，新创建内存空间，拷贝内容，相互不影响。 多层对象，每个对象都要实现Cloneable并重写clone()方法，都是调用super.clone()。

重写clone方法

@Override protected Object clone() throws CloneNotSupportedException { //浅拷贝,直接调用父类的clone()方法 return super.clone(); }

主对象重写clone方法

@Override protected Object clone() throws CloneNotSupportedException { //浅拷贝,直接调用父类的clone()方法 Student student = (Student) super.clone(); student.subject = (Subject) subject.clone(); return student; }