請實(shí)現(xiàn) copyRandomList 函數(shù)，復(fù)制一個(gè)復(fù)雜鏈表。在復(fù)雜鏈表中，每個(gè)節(jié)點(diǎn)除了有一個(gè) next 指針指向下一個(gè)節(jié)點(diǎn)，還有一個(gè) random 指針指向鏈表中的任意節(jié)點(diǎn)或者 null。

示例

• 輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

• 輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

• 解釋：給定的鏈表為空（空指針），因此返回 null。

提示

• -10000 <= Node.val <= 10000

• Node.random 為空（null）或指向鏈表中的節(jié)點(diǎn)。

• 節(jié)點(diǎn)數(shù)目不超過 1000 。

方法一：回溯+哈希表

算法如下：

• 檢查當(dāng)前節(jié)點(diǎn)是否拷貝過：

• 如果沒有拷貝過，把當(dāng)前節(jié)點(diǎn)存放到存放到哈希表中，并遞歸創(chuàng)建 “當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)” 和 “當(dāng)前節(jié)點(diǎn)的隨機(jī)節(jié)點(diǎn)”；

• 如果已經(jīng)拷貝過，直接從哈希表中取出拷貝的節(jié)點(diǎn)的指針返回。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，其中 n 是鏈表的長度。對(duì)于每個(gè)節(jié)點(diǎn)，我們至多訪問其“后繼節(jié)點(diǎn)”和“隨機(jī)節(jié)點(diǎn)”各一次，均攤每個(gè)點(diǎn)至多被訪問兩次。

• 空間復(fù)雜度：O(n)，其中 n 是鏈表的長度。為哈希表的空間開銷。

方法二：迭代+節(jié)點(diǎn)拆分

算法如下：

1. 復(fù)制各節(jié)點(diǎn)，并構(gòu)建拼接鏈表，即：a→b→c 變?yōu)?a→a1→b→b1→c→c1；

2. 構(gòu)建各新節(jié)點(diǎn)的 random指向，經(jīng)過步驟一后，當(dāng)前節(jié)點(diǎn)的新節(jié)點(diǎn)的隨機(jī)節(jié)點(diǎn)對(duì)應(yīng)的是原隨機(jī)節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)，即：a.a1.random = a.random.next;

3. 拆分兩鏈表，即：a1.next = = a.next.next = b1。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，其中 n 是鏈表的長度。我們只需要遍歷該鏈表三次。

• 空間復(fù)雜度：O(1)。注意返回值不計(jì)入空間復(fù)雜度。

END

世上無難事，只要肯攀登在，贈(zèng)友人。

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。