資訊專欄INFORMATION COLUMN
摘要：棧迭代復(fù)雜度時間空間如果不算新鏈表的空間則是思路由于隨機指針有可能產(chǎn)生環(huán)路，我們不能直接沿著隨機指針的方向一個一個復(fù)制。同時我們又不能沿著指針直接復(fù)制，因為我們不知道隨機指針?biāo)赶虻男鹿?jié)點是哪個。
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.
時間 O(N) 空間 O(N) 如果不算新鏈表的空間則是O(1)
思路由于隨機指針有可能產(chǎn)生環(huán)路，我們不能直接沿著隨機指針的方向一個一個復(fù)制。同時我們又不能沿著next指針直接復(fù)制，因為我們不知道隨機指針?biāo)赶虻男鹿?jié)點是哪個。這里有個技巧，我們把復(fù)制的表一對一的插在舊表的每個節(jié)點后面，這樣在第二次遍歷鏈表時，我們就肯定知道隨機指針指向的新節(jié)點是哪個了，肯定是舊節(jié)點隨即指針指向的舊節(jié)點的下一個節(jié)點。然后我們再遍歷一遍，把新舊兩個鏈表分割開來就行了。
代碼public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null) return null;
RandomListNode n1 = head;
RandomListNode n2;
// 生成新節(jié)點并接在舊節(jié)點后面
while(n1!=null){
n2 = new RandomListNode(n1.label);
n2.next = n1.next;
n1.next = n2;
n1 = n1.next.next;
}
// 給新節(jié)點的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é)點分開
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://m.hztianpu.com/yun/64463.html
摘要：題目要求假設(shè)存在這樣一個鏈表，在鏈表的每一個節(jié)點中，除了記錄了自身值和指向下一個節(jié)點的指針，還有一個隨機指針指向鏈表中任意一個節(jié)點。所以可以在兩次遍歷后完成任務(wù)。最后一圈遍歷，我們調(diào)整指針，恢復(fù)原鏈表和塑造新鏈表。 題目要求 A linked list is given such that each node contains an additional random pointer ...
摘要：給定一個鏈表，每個節(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。要求返回這個鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對克隆列表的引用。確定隨機節(jié)點的關(guān)系之后再拆分鏈表。其時間復(fù)雜度為，空間復(fù)雜度為。 給定一個鏈表，每個節(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。 要求返回這個鏈表的深拷貝。 A linked list is g...
摘要：給定一個鏈表，每個節(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。要求返回這個鏈表的深拷貝。提示你必須返回給定頭的拷貝作為對克隆列表的引用。確定隨機節(jié)點的關(guān)系之后再拆分鏈表。其時間復(fù)雜度為，空間復(fù)雜度為。 給定一個鏈表，每個節(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。 要求返回這個鏈表的深拷貝。 A linked list is g...
摘要：大體意思就是，先復(fù)制到，順便將所有的放在再復(fù)制所有的到，順便將所有的放在最后令，令，將和分離，返回的頭結(jié)點 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...
閱讀 2116·2023-04-26 00:16
閱讀 3559·2021-11-15 11:38
閱讀 3239·2019-08-30 12:50
閱讀 3247·2019-08-29 13:59
閱讀 809·2019-08-29 13:54
閱讀 2600·2019-08-29 13:42
閱讀 3383·2019-08-26 11:45
閱讀 2249·2019-08-26 11:36
