復制帶隨機指針的鏈表

題目描述：給你一個長度為 n 的鏈表，每個節(jié)點包含一個額外增加的隨機指針 random ，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。

構造這個鏈表的 深拷貝。 深拷貝應該正好由 n 個 全新 節(jié)點組成，其中每個新節(jié)點的值都設為其對應的原節(jié)點的值。新節(jié)點的 next 指針和 random 指針也都應指向復制鏈表中的新節(jié)點，并使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態(tài)。復制鏈表中的指針都不應指向原鏈表中的節(jié)點 。

例如，如果原鏈表中有 X 和 Y 兩個節(jié)點，其中 X.random --> Y 。那么在復制鏈表中對應的兩個節(jié)點 x 和 y ，同樣有 x.random --> y 。

返回復制鏈表的頭節(jié)點。

用一個由 n 個節(jié)點組成的鏈表來表示輸入/輸出中的鏈表。每個節(jié)點用一個 [val, random_index] 表示：

• val：一個表示 Node.val 的整數(shù)。

• random_index：隨機指針指向的節(jié)點索引（范圍從 0 到 n-1）；如果不指向任何節(jié)點，則為 ?null 。 你的代碼 只 接受原鏈表的頭節(jié)點 head 作為傳入?yún)?shù)。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/ ??

著作權歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：鏈表遍歷

• 首先，如果鏈表為空，直接返回。

• 否則，按順序遍歷鏈表，用一個HashMap用來存舊的節(jié)點和copy節(jié)點映射，遍歷過程如下：

• 如果當前節(jié)點已經(jīng)copy過，則從mappings中??；否則copy一個；

• 判斷當前節(jié)點如果存在random指針，判斷當前節(jié)點的random已經(jīng)copy過，則從mappings中??；否則copy一個。

• 最后，返回copy的鏈表。

【每日寄語】 年輕的朋友們，當你們發(fā)現(xiàn)自己的專業(yè)自己走一條路不通的時候，不要拒絕其他的方向，因為很多時候，正是你陌生的那條路帶給你光明。