目錄

題目描述

方法一、使用哈希表

方法二、不使用哈希表

---

題目描述

?

問題的關鍵是，random指針指向的是原鏈表的結點，這個原鏈表的結點對應哪一個新鏈表的結點呢？有兩種辦法。一是用哈希表。另一種是復制原鏈表的每一個結點，并將新結點接在原結點的后面組成一個長度加倍的鏈表，這樣原結點的直接后繼就是該原結點對應的新結點。

方法一、使用哈希表

unordered_map<Node*,Node*> new_table;//鍵是原鏈表中的舊結點，值是新鏈表中的新結點

unordered_map<Node*,Node*> random_table;//鍵是原鏈表中的舊結點，值是該舊結點的random指針指向的結點

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {if(head == nullptr)return nullptr;unordered_map<Node*,Node*> new_table;//鍵是原鏈表中的舊結點，值是新鏈表中的新結點unordered_map<Node*,Node*> random_table;//鍵是原鏈表中的舊結點，值是該舊結點的random指針指向的結點Node* newHead = nullptr;Node* newTail = nullptr;Node* cur = head;//第一步，建立新鏈表while(cur){Node* node = new Node(cur->val);new_table.insert({cur,node});random_table.insert({cur,cur->random});if(newHead == nullptr){newHead = node;newTail = node;}else{newTail->next = node;newTail = node;}cur = cur->next;}//第二步，設置新鏈表結點的random指針for(const auto& [old_node,new_node] : new_table){if(random_table[old_node]){new_node->random = new_table[random_table[old_node]];}}return newHead;}
};

實際上前面做法中的random_table是可以不需要的。

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {if(head == nullptr)return nullptr;unordered_map<Node*,Node*> new_table;//鍵是原鏈表中的舊結點，值是新鏈表中的新結點Node* newHead = nullptr;Node* newTail = nullptr;Node* cur = head;//第一步，建立新鏈表while(cur){Node* node = new Node(cur->val);new_table.insert({cur,node});if(newHead == nullptr){newHead = node;newTail = node;}else{newTail->next = node;newTail = node;}cur = cur->next;}cur = head;Node* new_cur = newHead;//第二步，設置新鏈表結點的random指針while(cur){if(cur->random){new_cur->random = new_table[cur->random];}cur = cur->next;new_cur = new_cur->next;}return newHead;}
};

方法二、不使用哈希表

第一步，復制每一個舊結點，并將新結點接在舊結點的后面組成新舊結點交替出現的長度翻倍的大鏈表。

第二步，設置新結點的random指針。

第三步，從大鏈表中提取出新結點組成新鏈表，并將原鏈表復原。

需要著重強調的是，第二步和第三步必須分開來做。

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {if(head == nullptr)return nullptr;Node* cur = head;//復制每一個舊結點，并將新結點接在舊結點的后面while(cur){Node* node = new Node(cur->val);Node* temp = cur->next;node->next = cur->next;cur->next = node;cur = temp;}cur = head;//設置新結點的random指針while(cur){if(cur->random)cur->next->random = cur->random->next;cur = cur->next->next;//原鏈表向前走一位}Node* new_head = nullptr;Node* new_tail = nullptr;cur = head;//提取出新結點組成新鏈表，并將原鏈表復原while(cur){if(new_head == nullptr){new_head = cur->next;new_tail = cur->next;}else{new_tail->next = cur->next;new_tail = cur->next;}cur->next = cur->next->next;//復原原鏈表cur = cur->next;//原鏈表向前走一步}return new_head;}
};