九章演算法

撰文 | JZ

專欄 | 九章演算法

題目描述

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

返回一個深拷貝的鏈表。

演算法分析

深度拷貝一個普通鏈表的演算法非常簡單，因為每一個節點只有一個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)。

參考程序

面試官角度分析

這道題目能夠分析清楚兩個不同思路的時間複雜度和空間複雜度就能夠拿到hire。

LintCode相關練習題

http://www.lintcode.com/en/problem/clone-graph/

推薦閱讀：