A linked list is given such that each node contains an additional random
pointer which could point to any node in the list or null.
Return a deep copy of the list.
好麻煩的連結清單題T_T
首先說一下深拷貝和淺拷貝的差別，參考這篇博文：
深拷貝：在拷貝過程中，為新的變量申請新的空間，是以原來的變量不存在時，拷貝得到的變量還可以使用。
淺拷貝：在拷貝過程中，不為新變量申請新的空間，隻是把原來變量的位址給新的變量，原來的變量不存在時，拷貝得到變量也不能使用了。
是以在題目中，要做到兩點，第一原來的連結清單不能改變；第二，拷貝得到的連結清單要有自己完全獨立的記憶體空間，而不是隻是指向原來的連結清單。
解題思路思路參考：
但是這個部落格有個bug，就是恢複原來連結清單的next指針和建立新連結清單的random和next指針是不能同時進行的。因為有可能有如下情況：
在建立3‘的random指針的時候通過3‘目前的random指針找到3，又通過3的random指針找到1，但是如果1的next指針已經被改為指向2，而不再是1‘，那麼就沒辦法找到3‘真正的random指針1‘了，是以恢複原來連結清單的next指針，隻能在新連結清單完全建立好以後進行。那麼就需要一個結構來存儲原來連結清單的next指針資訊，這裡采用一個map：oldlistnext儲存。
是以算法分為3個循環：
第一個循環，建立新的連結清單，并且把新連結清單中各個節點的random指針指向原來連結清單對應的節點，原來連結清單的next指針指向新連結清單的對應節點，如下圖所示：
圖中橙色是原來連結清單的next指針，綠色是建立連結清單的random指針,藍色虛線表示建立連結清單的next指針。
第二個循環，恢複建立連結清單的next和random指針：new_list_p->next =
new_list_p->next->next;new_list_p->random
= new_list_p->random->random->next;如下圖所示：
第三個循環，恢複原來連結清單的next指針，old_list_p->next = oldlistnext[old_list_p]，如下圖所示：
當然，上述過程中要注意各種邊界情況的考慮。
代碼如下：