剑指offer 第25题 复杂链表的复制
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
根据题意:当传入的是1,输出的结果应该是1’,等等
思路:利用hashmap存储的是键值对特点。HashMap<String,String> map = new HashMap<>();map.put(1,2);map.get(1);
我们将1和1对应的1’存放到map中,2和2对应的2’存放到map中,3和3对应得3’存放到map中。通过1的next指针可以找到2,而通过哈希表可以找到2对应的2’,所以的1’的next指针连接到2’,同时因为1的random指针可以连接到3,通过hashmap可以找到3对应的3’,然后将1’的random指针连接到3’。然后遍历2重复以上过程,就可以得到整个链表的复制,并且通过哈希表中键可以自动找到对应的值。
代码如下:
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 static RandomListNode Clone(RandomListNode pHead){
HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
RandomListNode cur = pHead;
while(cur!=null){
map.put(cur, new RandomListNode(cur.label)); //cur是原链表中的节点,new RandomListNode(cur.label)是新生成的 拷贝节点 ,并将它们放在map中
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); //返回原始头节点的拷贝节点
}
}