<abbr id="aaags"></abbr>

【刷算法】復雜鏈表的復制

Mike617 發布于2019-08-22 18:32 / 1733人閱讀

摘要：題目描述輸入一個復雜鏈表每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點，返回結果為復制后復雜鏈表的。

題目描述

輸入一個復雜鏈表（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），返回結果為復制后復雜鏈表的head。

分析

常規的復制鏈表只需要考慮每個節點的next指針即可，但是該題還有另外一個random指針，且沒有規律，可能指向任何其他節點，此時需要解決的問題是如何復制random指針。開始想先通過next指針構建新的鏈表，同時使用棧保存各個新節點，然后再通過棧來構建random指針，但是發現過程中并沒有這么簡單，比如對于A.random=C來說，那么在新鏈表中就是A1.random=C1，我無法在新鏈表中以O(1)的時間復雜度訪問C1，所以我這種方法受阻。

在網上查到一種思路，遍歷鏈表的時候把每個新節點添加在舊節點的后面，比如 A->B->C，復制完是A->A1->B->B1->C->C1，然后對于每個復制節點來說來說，A1.random=A.random.next，B1.random=B.random.next，C1.random=C.random.next，完美的解決了復制random指針時獲取到目標節點的問題。最后再拆成兩條鏈表即可。

代碼實現

/*function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}*/
function Clone(h)
{
    if(h === null)
        return h;
    var cur = h;
    // 第一次遍歷，先復制所有節點，且把復制節點添加到相應節點后面
    while(cur !== null) {
        var node = new RandomListNode(cur.label);
        node.next = cur.next;
        cur.next = node;
        cur = node.next;
    }
    
    cur = h;
    // 第二次遍歷，復制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;
}

GPU云服務器云服務器 linux鏈表的安全訪問合并鏈表的c語言學生鏈表的c語言代碼關于鏈表的c語言代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/95978.html

Leetcode：刷完31道鏈表題的一點總結

摘要：既然說到地址空間了就順帶說一下上面環形鏈表這道題的另一種很的解法吧。介紹完常規操作鏈表的一些基本知識點后，現在回到快慢指針。 ??前幾天第一次在 Segmentfault 發文—JavaScript：十大排序的算法思路和代碼實現，發現大家似乎挺喜歡算法的，所以今天再分享一篇前兩個星期寫的 Leetcode 刷題總結，希望對大家能有所幫助。 ??本文首發于我的blog 前言 ??今天終于...

DevTalking 2019-08-23 17:50 評論0 收藏0
【刷算法】LeetCode.19-刪除鏈表的倒數第N個節點

摘要：題目描述給定一個鏈表，刪除鏈表的倒數第個節點，并且返回鏈表的頭結點。示例給定一個鏈表和當刪除了倒數第二個節點后，鏈表變為說明給定的保證是有效的。題目描述給定一個鏈表，刪除鏈表的倒數第 n 個節點，并且返回鏈表的頭結點。示例：給定一個鏈表: 1->2->3->4->5, 和 n = 2. 當刪除了倒數第二個節點后，鏈表變為 1->2->3->5. 說明：給定的 n 保證是有效...

Binguner 2019-08-23 11:37 評論0 收藏0
＜LeetCode天梯＞Day025 刪除鏈表的倒數第N個節點（雙指針） | 初級算法 | Pyth

摘要：示例輸入輸出示例輸入輸出示例輸入輸出提示雙指針法分析根據題干的要求，我們需要刪除倒數第個節點，在返回頭結點。只需要找到倒數第個節點，將其刪除，再返回。 ?作者簡...

andot 2021-11-16 11:45 評論0 收藏0