題目描述:
給定一個連結清單，每個節點包含一個額外增加的随機指針，該指針可以指向連結清單中的任何節點或空節點。
要求傳回這個連結清單的深度拷貝。
思路:
先周遊連結清單,将每個節點對應的随機指針指向的對象利用HashMap存起來,key的值就為節點的在連結清單裡面的位置,Value的值是随機指針指向的對象
再把原連結清單的節點對應的在連結清單中的位置存起來,key為節點對象,然後将節點的label取出來建立節點,存起來
再次周遊連結清單,處理随機指針
這是第一種用HashMap的辦法,但是性能不行,還有優化的空間,之後我再研究研究看能不能改改
public static RandomListNode copyRandomList(RandomListNode head) {
HashMap randomMap = new HashMap<>();//随機節點
HashMap newMap = new HashMap<>();//新的節點
HashMap oldMap = new HashMap<>();//原表的節點
RandomListNode result = head;
if(head==null)
return head;
if(head.next==null){
RandomListNode it = new RandomListNode(head.label);
if (head.random!=null){
it.random = it;//指向自己
}
return it;
}
//疊代
RandomListNode iterator = head;
int i = 0;
while(iterator!=null){
//将第幾位對應的随機指針存起來
randomMap.put(i,iterator.random);
//原連結清單節點對應的位置存起來
oldMap.put(iterator,i);
//建立節點,複制
RandomListNode node = new RandomListNode(iterator.label);
newMap.put(i,node);
if(i==0){
//第一個
result = node;
}
iterator = iterator.next;
i++;
}
i = 0;
iterator = head;
while(iterator!=null){
if(i>0)
newMap.get(i-1).next = newMap.get(i);
//檢測原節點的随機指針是否為空
if(oldMap.get(randomMap.get(i))!=null){
//獲得原連結清單節點的随機指針指向的對象的位置
int random = oldMap.get(randomMap.get(i));
//指派
newMap.get(i).random = newMap.get(random);
}else {
//随機指針為空的情況
newMap.get(i).random = null;
}
iterator = iterator.next;
i++;
}
return result;
}
static class RandomListNode {
int label;
RandomListNode next, random;
RandomListNode(int x) { this.label = x; }
}
還有不用HashMap的,性能應該好點我還沒AC.AC了再傳上來...不知道怎麼錯了