溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關Linkedin中如何復制隨機指針，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。
題目描述
給出一個鏈表，每個節點包含一個額外增加的隨機指針可以指向鏈表中的任何節點或空的節點。
返回一個深拷貝的鏈表。
算法分析
深度拷貝一個普通鏈表的算法非常簡單，因為每一個節點只有一個next指針指向下一個節點，整體上是一個線性結構；但是題目中的節點多了一個隨機指針，可以指向鏈表中的任何節點，或者是空的節點。所以在建立新的鏈表的時候，要考慮到隨機指針指向的節點是否已經被新建過了，是否已經存在于新鏈表中。
1. 需要查重的時候，自然想到了散列表（哈希表），所以每次新建一個節點時，都將原鏈表里的節點和新的節點放入HashMap中，以原節點為鍵，新節點為值，這樣在復制next指針指向的節點、或者是random指針指向的節點時，都可以在O(1)的時間內在散列表中找到已經復制過并放入新鏈表中的新節點。這個算法的時間復雜度是O(N)，額外空間復雜度是O(N)。
2. 使用散列表雖好，但是會占用O(N)的額外空間，如果可以使用常數級別的額外空間就最好了。方法一中占用空間的是新建的散列表HashMap，如果可以用別的方法將原節點與新節點聯系起來，在O(1)的時間內可以找到對應的節點，就可以不使用散列表了。因為題目中已經告知隨機指針只會指向鏈表中的節點或者是空節點，對于這一特性，每次在建立新節點時，將新節點插入到舊鏈表中相應的節點后面，如舊鏈表1→2->3→4，在遍歷和插入之后就會變成1->1'->2->2'->3->3'->4->4'；而第二次遍歷時將新節點里的random指針指向舊節點random指針指向的節點的next，如果在鏈表1->1'->2->2'->3->3'->4->4'中，節點4的random指針指向了節點1，那么就讓節點4的next (4')的random指向節點1的next (1')；最后再遍歷鏈表，將新的節點都取出來，組成新的鏈表。這個算法的時間復雜度是O(3N) = O(N)，額外空間復雜度是O(1)。
參考程序
關于Linkedin中如何復制隨機指針就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
