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