劍指 Offer 35. 複雜鏈表的複製
劍指 Offer 35. 複雜鏈表的複製
請實現 copyRandomList 函數，複製一個複雜鏈表。在複雜鏈表中，每個節點除了有一個 next 指針指向下一個節點，還有一個 random 指針指向鏈表中的任意節點或者 null。
示例 1：
輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]
示例 3：
輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]
示例 4：
輸入：head = []
輸出：[]
解釋：給定的鏈表為空（空指針），因此返回 null。
提示：
- -10000 <= Node.val <= 10000
- Node.random 為空（null）或指向鏈表中的節點。
- 節點數目不超過 1000 。
首先說明解題思路的時候，先簡單說一下這個題主要是讓返回的值是你自行複製的鏈表，也就是說可以採用暴力解法、哈希表或者開闢一個空間來創建一個鏈表讓它進行返回，當然直接return head肯定不行。
一、暴力解法
這個暴力解法在LeetCode裏面提交題解的時候，提示超出了時間限制，然後看了K神的代碼以後，發現還可以再精簡完善一些。
class Solution {
public Node copyRandomList(Node head) {
if(head==null) return null;
ArrayList<Node> list = new ArrayList<>();
while(head!=null){
list.add(head);
head = head.next;
}
//創建結果集合併初始化
ArrayList<Node> res = new ArrayList<>();
for(int i = 0;i<list.size();++i){
res.add(new Node(list.get(i).val));
}
//設置結果結合的 random和next
for (int i = 0; i < list.size(); ++i) {
res.get(i).random = list.get(i).random == null?null:res.get(list.indexOf(list.get(i).random));
if(i!=list.size()-1) res.get(i).next = res.get(i+1);
}
return res.get(0);
}
}
二、哈希表
這裡主要的難點在看懂構建新鏈表的引用指向：
- 構建新節點的next和random引用指向
- cur遍歷原鏈表到下一個節點
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
Node cur = head;
Map<Node,Node> res = new HashMap<>();
while(cur != null) {//遍歷鏈表,並存儲每個節點的新節點
res.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;//重置cur
while (cur != null) {
res.get(cur).next = res.get(cur.next);//用cur.next指向res.get(cur).next
res.get(cur).random = res.get(cur.random);//用cur.random指向res.get(cur).random
cur = cur.next;
}
return res.get(head);//返回頭結點是因為新鏈表的頭結點也存着在res中
}
}
三、遞歸
這個做題思路類似於dfs，創建一個節點之後，接着通過遞歸的方式創建他的next節點……（參考鏈接見下面）
class Solution {
public Node copyRandomList(Node head) {
//map存儲已經創建的節點
HashMap<Node, Node> map = new HashMap<>();
return copyListHelper(head, map);
}
public Node copyListHelper(Node head, HashMap<Node, Node> map) {
if (head == null)
return null;
//如果節點創建了，直接從map中取
if (map.containsKey(head))
return map.get(head);
//如果節點沒有創建，就創建一個，然後使用遞歸的方式在創建他的
//next節點和random節點
Node res = new Node(head.val);
map.put(head, res);
res.next = copyListHelper(head.next, map);
res.random = copyListHelper(head.random, map);
return res;
}
}
參考鏈接：
//leetcode-cn.com/leetbook/read/illustration-of-algorithm/9plk45/
