資訊專欄INFORMATION COLUMN
摘要：棧迭代復(fù)雜度時(shí)間空間如果不算新鏈表的空間則是思路由于隨機(jī)指針有可能產(chǎn)生環(huán)路，我們不能直接沿著隨機(jī)指針的方向一個(gè)一個(gè)復(fù)制。同時(shí)我們又不能沿著指針直接復(fù)制，因?yàn)槲覀儾恢离S機(jī)指針?biāo)赶虻男鹿?jié)點(diǎn)是哪個(gè)。
Copy List with Random Pointer
棧迭代 復(fù)雜度A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
時(shí)間 O(N) 空間 O(N) 如果不算新鏈表的空間則是O(1)
思路由于隨機(jī)指針有可能產(chǎn)生環(huán)路，我們不能直接沿著隨機(jī)指針的方向一個(gè)一個(gè)復(fù)制。同時(shí)我們又不能沿著next指針直接復(fù)制，因?yàn)槲覀儾恢离S機(jī)指針?biāo)赶虻男鹿?jié)點(diǎn)是哪個(gè)。這里有個(gè)技巧，我們把復(fù)制的表一對一的插在舊表的每個(gè)節(jié)點(diǎn)后面，這樣在第二次遍歷鏈表時(shí)，我們就肯定知道隨機(jī)指針指向的新節(jié)點(diǎn)是哪個(gè)了，肯定是舊節(jié)點(diǎn)隨即指針指向的舊節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。然后我們再遍歷一遍，把新舊兩個(gè)鏈表分割開來就行了。
代碼public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null) return null;
RandomListNode n1 = head;
RandomListNode n2;
// 生成新節(jié)點(diǎn)并接在舊節(jié)點(diǎn)后面
while(n1!=null){
n2 = new RandomListNode(n1.label);
n2.next = n1.next;
n1.next = n2;
n1 = n1.next.next;
}
// 給新節(jié)點(diǎn)的random字段賦值
n1 = head;
n2 = n1.next;
while(n1!=null){
n2.random = n1.random != null ? n1.random.next : null;
n1 = n1.next.next;
n2 = n1 != null ? n2.next.next : null;
}
n1 = head;
n2 = n1.next;
RandomListNode res = n2;
// 將新舊節(jié)點(diǎn)分開
while(n1!=null){
n1.next = n1.next.next;
n2.next = n2.next != null ? n2.next.next : null;
n1 = n1.next;
n2 = n2.next;
}
return res;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64463.html
摘要：題目要求假設(shè)存在這樣一個(gè)鏈表，在鏈表的每一個(gè)節(jié)點(diǎn)中，除了記錄了自身值和指向下一個(gè)節(jié)點(diǎn)的指針，還有一個(gè)隨機(jī)指針指向鏈表中任意一個(gè)節(jié)點(diǎn)。所以可以在兩次遍歷后完成任務(wù)。最后一圈遍歷，我們調(diào)整指針，恢復(fù)原鏈表和塑造新鏈表。 題目要求 A linked list is given such that each node contains an additional random pointer ...
摘要：給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。要求返回這個(gè)鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對克隆列表的引用。確定隨機(jī)節(jié)點(diǎn)的關(guān)系之后再拆分鏈表。其時(shí)間復(fù)雜度為，空間復(fù)雜度為。 給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。 要求返回這個(gè)鏈表的深拷貝。 A linked list is g...
摘要：給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。要求返回這個(gè)鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對克隆列表的引用。確定隨機(jī)節(jié)點(diǎn)的關(guān)系之后再拆分鏈表。其時(shí)間復(fù)雜度為，空間復(fù)雜度為。 給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。 要求返回這個(gè)鏈表的深拷貝。 A linked list is g...
摘要：大體意思就是，先復(fù)制到，順便將所有的放在再復(fù)制所有的到，順便將所有的放在最后令，令，將和分離，返回的頭結(jié)點(diǎn) Problem A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. ...
LeetCode[138] Copy List with Random Pointer A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of t...
閱讀 2054·2023-04-26 00:16
閱讀 3513·2021-11-15 11:38
閱讀 3202·2019-08-30 12:50
閱讀 3211·2019-08-29 13:59
閱讀 779·2019-08-29 13:54
閱讀 2543·2019-08-29 13:42
閱讀 3339·2019-08-26 11:45
閱讀 2216·2019-08-26 11:36
