這篇文章將為大家詳細講解有關Linkedin中如何復制隨機指針，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

內蒙古網站制作公司哪家好，找創新互聯！從網頁設計、網站建設、微信開發、APP開發、自適應網站建設等網站項目制作，到程序開發，運營維護。創新互聯成立與2013年到現在10年的時間，我們擁有了豐富的建站經驗和運維經驗，來保證我們的工作的順利進行。專注于網站建設就選創新互聯。

題目描述 

給出一個鏈表，每個節點包含一個額外增加的隨機指針可以指向鏈表中的任何節點或空的節點。

返回一個深拷貝的鏈表。

算法分析 

深度拷貝一個普通鏈表的算法非常簡單，因為每一個節點只有一個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中如何復制隨機指針就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

網頁名稱：Linkedin中如何復制隨機指針
URL地址：http://vcdvsql.cn/article30/iigipo.html

成都網站建設公司_創新互聯，為您提供服務器托管、面包屑導航、網站維護、微信公眾號、建站公司、網站內鏈

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯