資訊專欄INFORMATION COLUMN
摘要：題目描述輸入一個復(fù)雜鏈表每個節(jié)點中有節(jié)點值，以及兩個指針，一個指向下一個節(jié)點，另一個特殊指針指向任意一個節(jié)點，返回結(jié)果為復(fù)制后復(fù)雜鏈表的。
題目描述
輸入一個復(fù)雜鏈表（每個節(jié)點中有節(jié)點值，以及兩個指針，一個指向下一個節(jié)點，另一個特殊指針指向任意一個節(jié)點），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。
分析常規(guī)的復(fù)制鏈表只需要考慮每個節(jié)點的next指針即可，但是該題還有另外一個random指針，且沒有規(guī)律，可能指向任何其他節(jié)點，此時需要解決的問題是如何復(fù)制random指針。開始想先通過next指針構(gòu)建新的鏈表，同時使用棧保存各個新節(jié)點，然后再通過棧來構(gòu)建random指針，但是發(fā)現(xiàn)過程中并沒有這么簡單，比如對于A.random=C來說，那么在新鏈表中就是A1.random=C1，我無法在新鏈表中以O(shè)(1)的時間復(fù)雜度訪問C1，所以我這種方法受阻。
在網(wǎng)上查到一種思路，遍歷鏈表的時候把每個新節(jié)點添加在舊節(jié)點的后面，比如 A->B->C，復(fù)制完是A->A1->B->B1->C->C1，然后對于每個復(fù)制節(jié)點來說來說，A1.random=A.random.next，B1.random=B.random.next，C1.random=C.random.next，完美的解決了復(fù)制random指針時獲取到目標(biāo)節(jié)點的問題。最后再拆成兩條鏈表即可。
/*function RandomListNode(x){
this.label = x;
this.next = null;
this.random = null;
}*/
function Clone(h)
{
if(h === null)
return h;
var cur = h;
// 第一次遍歷，先復(fù)制所有節(jié)點，且把復(fù)制節(jié)點添加到相應(yīng)節(jié)點后面
while(cur !== null) {
var node = new RandomListNode(cur.label);
node.next = cur.next;
cur.next = node;
cur = node.next;
}
cur = h;
// 第二次遍歷，復(fù)制random指針
while(cur !== null) {
if(cur.random !== null){
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
var clonedH = h.next;
var temp;
cur = h;
// 第三次遍歷，把鏈表拆開
while(cur.next !== null) {
temp = cur.next;
cur.next = cur.next.next;
cur = temp;
}
return clonedH;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/95978.html
摘要：既然說到地址空間了就順帶說一下上面環(huán)形鏈表這道題的另一種很的解法吧。介紹完常規(guī)操作鏈表的一些基本知識點后，現(xiàn)在回到快慢指針。 ??前幾天第一次在 Segmentfault 發(fā)文—JavaScript：十大排序的算法思路和代碼實現(xiàn)，發(fā)現(xiàn)大家似乎挺喜歡算法的，所以今天再分享一篇前兩個星期寫的 Leetcode 刷題總結(jié)，希望對大家能有所幫助。 ??本文首發(fā)于我的blog 前言 ??今天終于...
摘要：題目描述給定一個鏈表，刪除鏈表的倒數(shù)第個節(jié)點，并且返回鏈表的頭結(jié)點。示例給定一個鏈表和當(dāng)刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)檎f明給定的保證是有效的。 題目描述 給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。 示例： 給定一個鏈表: 1->2->3->4->5, 和 n = 2. 當(dāng)刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5. 說明： 給定的 n 保證是有效...
摘要：示例輸入輸出示例輸入輸出示例輸入輸出提示雙指針法分析根據(jù)題干的要求，我們需要刪除倒數(shù)第個節(jié)點，在返回頭結(jié)點。只需要找到倒數(shù)第個節(jié)點，將其刪除，再返回。 ?作者簡...
閱讀 2481·2021-11-19 09:59
閱讀 2005·2019-08-30 15:55
閱讀 938·2019-08-29 13:30
閱讀 1342·2019-08-26 10:18
閱讀 3091·2019-08-23 18:36
閱讀 2394·2019-08-23 18:25
閱讀 1168·2019-08-23 18:07
閱讀 441·2019-08-23 17:15
