「複製帶隨機指針的鏈表」的一個很巧妙解法

題目來源於 LeetCode 上第 138 號問題：複製帶隨機指針的鏈表。題目難度為 Medium，目前通過率為 40.5% 。

題目描述

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

要求返回這個鏈表的深拷貝。

題目解析

1. 在原鏈表的每個節點後面拷貝出一個新的節點
2. 依次給新的節點的隨機指針賦值：cur->next->random = cur->random->next
3. 斷開鏈表可得到深度拷貝後的新鏈表

之所以說這個方法比較巧妙是因為相較於一般的解法（如使用 Hash map ）來處理，上面這個解法 不需要佔用額外的空間。

動畫描述

代碼實現

我發現帶指針的題目使用 C++ 版本更容易描述，所以下面的代碼實現是 C++ 版本。

class Solution {
public:
 RandomListNode *copyRandomList(RandomListNode *head) {
 if (!head) return NULL;
 RandomListNode *cur = head;
 while (cur) {
 RandomListNode *node = new RandomListNode(cur->label);
 node->next = cur->next;
 cur->next = node;
 cur = node->next;
 }
 cur = head;
 while (cur) {
 if (cur->random) {
 cur->next->random = cur->random->next;
 }
 cur = cur->next->next;
 }
 cur = head;
 RandomListNode *res = head->next;
 while (cur) {
 RandomListNode *tmp = cur->next;
 cur->next = tmp->next;
 if(tmp->next) tmp->next = tmp->next->next;
 cur = cur->next;
 }
 return res;
 }
};

閱讀更多 五分鐘學算法 的文章

關鍵字: tmp 指針 RandomListNode