[LeetCode] 138. Copy List with Random Pointer 拷貝帶有隨機(jī)指針的鏈表

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.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}  Explanation: Node 1's value is 1, both of its next and random pointer points to Node 2. Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

1. You must return the copy of the given head as a reference to the cloned list.

這道鏈表的深度拷貝題的難點(diǎn)就在于如何處理隨機(jī)指針的問題，由于每一個(gè)節(jié)點(diǎn)都有一個(gè)隨機(jī)指針，這個(gè)指針可以為空，也可以指向鏈表的任意一個(gè)節(jié)點(diǎn)，如果在每生成一個(gè)新節(jié)點(diǎn)給其隨機(jī)指針賦值時(shí)，都要去遍歷原鏈表的話，OJ 上肯定會(huì)超時(shí)，所以可以考慮用 HashMap 來縮短查找時(shí)間，第一遍遍歷生成所有新節(jié)點(diǎn)時(shí)同時(shí)建立一個(gè)原節(jié)點(diǎn)和新節(jié)點(diǎn)的 HashMap，第二遍給隨機(jī)指針賦值時(shí)，查找時(shí)間是常數(shù)級(jí)。代碼如下：

解法一：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        Node *res = new Node(head->val, nullptr, nullptr);
        Node *node = res, *cur = head->next;
        unordered_map<Node*, Node*> m;
        m[head] = res;
        while (cur) {
            Node *t = new Node(cur->val, nullptr, nullptr);
            node->next = t;
            m[cur] = t;
            node = node->next;
            cur = cur->next;
        }
        node = res; cur = head;
        while (cur) {
            node->random = m[cur->random];
            node = node->next;
            cur = cur->next;
        }
        return res;
    }
};

我們可以使用遞歸的解法，寫起來相當(dāng)?shù)暮?jiǎn)潔，還是需要一個(gè) HashMap 來建立原鏈表結(jié)點(diǎn)和拷貝鏈表結(jié)點(diǎn)之間的映射。在遞歸函數(shù)中，首先判空，若為空，則返回空指針。然后就是去 HashMap 中查找是否已經(jīng)在拷貝鏈表中存在了該結(jié)點(diǎn)，是的話直接返回。否則新建一個(gè)拷貝結(jié)點(diǎn) res，然后建立原結(jié)點(diǎn)和該拷貝結(jié)點(diǎn)之間的映射，然后就是要給拷貝結(jié)點(diǎn)的 next 和 random 指針賦值了，直接分別調(diào)用遞歸函數(shù)即可，參見代碼如下：

解法二：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> m;
        return helper(head, m);
    }
    Node* helper(Node* node, unordered_map<Node*, Node*>& m) {
        if (!node) return nullptr;
        if (m.count(node)) return m[node];
        Node *res = new Node(node->val, nullptr, nullptr);
        m[node] = res;
        res->next = helper(node->next, m);
        res->random = helper(node->random, m);
        return res;
    }
};

當(dāng)然，如果使用 HashMap 占用額外的空間，如果這道題限制了空間的話，就要考慮別的方法。下面這個(gè)方法很巧妙，可以分為以下三個(gè)步驟：

1. 在原鏈表的每個(gè)節(jié)點(diǎn)后面拷貝出一個(gè)新的節(jié)點(diǎn)。

2. 依次給新的節(jié)點(diǎn)的隨機(jī)指針賦值，而且這個(gè)賦值非常容易 cur->next->random = cur->random->next。

3. 斷開鏈表可得到深度拷貝后的新鏈表。

舉個(gè)例子來說吧，比如原鏈表是 1(2) -> 2(3) -> 3(1)，括號(hào)中是其 random 指針指向的結(jié)點(diǎn)，那么這個(gè)解法是首先比遍歷一遍原鏈表，在每個(gè)結(jié)點(diǎn)后拷貝一個(gè)同樣的結(jié)點(diǎn)，但是拷貝結(jié)點(diǎn)的 random 指針仍為空，則原鏈表變?yōu)?1(2) -> 1(null) -> 2(3) -> 2(null) -> 3(1) -> 3(null)。然后第二次遍歷，是將拷貝結(jié)點(diǎn)的 random 指針賦上正確的值，則原鏈表變?yōu)?#160;1(2) -> 1(2) -> 2(3) -> 2(3) -> 3(1) -> 3(1)，注意賦值語句為：

cur->next->random = cur->random->next;

這里的 cur 是原鏈表中結(jié)點(diǎn)，cur->next 則為拷貝鏈表的結(jié)點(diǎn)，cur->next->random 則為拷貝鏈表的 random 指針。cur->random 為原鏈表結(jié)點(diǎn)的 random 指針指向的結(jié)點(diǎn)，因?yàn)槠渲赶虻倪€是原鏈表的結(jié)點(diǎn)，所以我們要再加個(gè) next，才能指向拷貝鏈表的結(jié)點(diǎn)。最后再遍歷一次，就是要把原鏈表和拷貝鏈表斷開即可，參見代碼如下：

解法二：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        Node *cur = head;
        while (cur) {
            Node *t = new Node(cur->val, nullptr, nullptr);
            t->next = cur->next;
            cur->next = t;
            cur = t->next;
        }
        cur = head;
        while (cur) {
            if (cur->random) cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        cur = head;
        Node *res = head->next;
        while (cur) {
            Node *t = cur->next;
            cur->next = t->next;
            if (t->next) t->next = t->next->next;
            cur = cur->next;
        }
        return res;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/138

參考資料：

Clone Graph

類似題目：

https://leetcode.com/problems/copy-list-with-random-pointer/

https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43488/Java-O(n)-solution

https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43567/C%2B%2B-simple-recursive-solution

https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43491/A-solution-with-constant-space-complexity-O(1)-and-linear-time-complexity-O(N)

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(138.拷貝帶有隨機(jī)指針的鏈表)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)拷貝帶有隨機(jī)指針的鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！