##題目描述 輸入一個復雜鏈表（每個節點中有節點值，以及兩個指標，一個指向下一個節點，另一個特殊指標指向任意一個節點），回傳結果為復制后復雜鏈表的head， （注意，輸出結果中請不要回傳引數中的節點參考，否則判題程式會直接回傳空）不能改動原鏈表
思路
-
鏈表操作
時間復雜度O(n)，空間復雜度O(1)， -
HashMap
使用HashMap復制結點關系
時間復雜度O(n)，空間復雜度O(1)，
鏈表操作代碼
/*
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 p = pHead;
// 在原有結點之后新增復制結點
while(p != null) {
RandomListNode node = new RandomListNode(p.label);
node.next = p.next;
p.next = node;
p = p.next.next;
}
// 復制隨機指標
p = pHead;
while(p != null) {
p.next.random = p.random == null ? null : p.random.next;
p = p.next.next;
}
// 摘鏈
RandomListNode head = pHead.next;
RandomListNode q = pHead;
p = pHead.next;
while(q != null) {
q.next = p.next;
q = q.next;
// 空指標的判斷
p.next = q == null ? null : q.next;
p = p.next;
}
return head;
}
}
HashMap代碼
import java.util.HashMap;
/*
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;
HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
RandomListNode p = pHead;
while(p != null) {
map.put(p, new RandomListNode(p.label));
p = p.next;
}
p = pHead;
while(p != null) {
if(p.next != null) {
// 不存在Hash值情況的考慮
map.get(p).next = map.get(p.next);
} else {
map.get(p).next = null;
}
// 根據題意，指向任意一個結點，不存在null的情況
map.get(p).random = map.get(p.random);
p = p.next;
}
return map.get(pHead);
}
}
筆記
q在回圈體內做了改變，在下一次回圈前又被使用，需要在回圈體內判斷，HashMap的get索引同理，
while(q != null) {
q.next = p.next;
q = q.next;
// 空指標的判斷
p.next = q == null ? null : q.next;
p = p.next;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85172.html
標籤：其他
上一篇：Codeforces 1301B Motarack's Birthday（二分）
下一篇：二叉搜索樹與雙向鏈表