题解 | #复杂链表的复制#
复杂链表的复制
http://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
暴力解法
import java.util.*;
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if(pHead == null){
return null;
}
RandomListNode node = pHead;
List<RandomListNode> nodeList = new ArrayList<>();
Map<RandomListNode, Integer> nodeMap = new HashMap<>();
List<RandomListNode> newNodeList = new ArrayList<>();
while (node != null){
nodeList.add(node);
newNodeList.add(node);
nodeMap.put(node,nodeList.size() - 1);
node = node.next;
}
for(int i = nodeList.size() - 1; i >= 0; i--){
RandomListNode newNode = new RandomListNode(nodeList.get(i).label);
newNodeList.set(i, newNode);
if(i < nodeList.size() - 1){
newNode.next = newNodeList.get(i + 1);
}
}
for(int j = 0; j < newNodeList.size(); j++){
Integer temp = nodeMap.get(nodeList.get(j).random);
if(temp == null){
newNodeList.get(j).random = null;
}else{
newNodeList.get(j).random = newNodeList.get(temp);
}
}
return newNodeList.get(0);
}
}
