题解 | #复杂链表复制#
复杂链表的复制
http://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.* ;
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if(pHead == null) {
return null ;
}
RandomListNode c = pHead ;
RandomListNode pre = new RandomListNode(0) ;
RandomListNode n = pre ;
//思路就是：将 1.旧结点：新节点 存入 map
2.再次遍历旧链表与新链表，要找到新节点对应的random，就是旧结点的random对应的新节点
//旧结点：新结点
HashMap<RandomListNode , RandomListNode> map = new HashMap<>() ;
while(c != null) {
RandomListNode newNode = new RandomListNode(c.label) ;
map.put(c,newNode) ;
n.next = newNode ;
n = n.next ;
c = c.next ;
}
c = pHead ;
n = pre.next ;
while(c != null) {
n.random = map.get(c.random);
n = n.next ;
c = c.next ;
}
return pre.next ;
}
}
一个菜鸟的算法刷题记录 文章被收录于专栏
分享一个菜鸟的成长记录
