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

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

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

返回一個深拷貝的鏈表。

深度拷貝一個普通鏈表的算法非常簡單，因為每一個節(jié)點只有一個next指針指向下一個節(jié)點，整體上是一個線性結(jié)構(gòu)；但是題目中的節(jié)點多了一個隨機指針，可以指向鏈表中的任何節(jié)點，或者是空的節(jié)點。所以在建立新的鏈表的時候，要考慮到隨機指針指向的節(jié)點是否已經(jīng)被新建過了，是否已經(jīng)存在于新鏈表中。

1. 需要查重的時候，自然想到了散列表（哈希表），所以每次新建一個節(jié)點時，都將原鏈表里的節(jié)點和新的節(jié)點放入HashMap中，以原節(jié)點為鍵，新節(jié)點為值，這樣在復(fù)制next指針指向的節(jié)點、或者是random指針指向的節(jié)點時，都可以在O(1)的時間內(nèi)在散列表中找到已經(jīng)復(fù)制過并放入新鏈表中的新節(jié)點。這個算法的時間復(fù)雜度是O(N)，額外空間復(fù)雜度是O(N)。

2. 使用散列表雖好，但是會占用O(N)的額外空間，如果可以使用常數(shù)級別的額外空間就最好了。方法一中占用空間的是新建的散列表HashMap，如果可以用別的方法將原節(jié)點與新節(jié)點聯(lián)系起來，在O(1)的時間內(nèi)可以找到對應(yīng)的節(jié)點，就可以不使用散列表了。因為題目中已經(jīng)告知隨機指針只會指向鏈表中的節(jié)點或者是空節(jié)點，對于這一特性，每次在建立新節(jié)點時，將新節(jié)點插入到舊鏈表中相應(yīng)的節(jié)點后面，如舊鏈表1→2->3→4，在遍歷和插入之后就會變成1->1'->2->2'->3->3'->4->4'；而第二次遍歷時將新節(jié)點里的random指針指向舊節(jié)點random指針指向的節(jié)點的next，如果在鏈表1->1'->2->2'->3->3'->4->4'中，節(jié)點4的random指針指向了節(jié)點1，那么就讓節(jié)點4的next (4')的random指向節(jié)點1的next (1')；最后再遍歷鏈表，將新的節(jié)點都取出來，組成新的鏈表。這個算法的時間復(fù)雜度是O(3N) = O(N)，額外空間復(fù)雜度是O(1)。

關(guān)于Linkedin中如何復(fù)制隨機指針就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。