[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ī)指針的問題，由于每一個節(jié)點(diǎn)都有一個隨機(jī)指針，這個指針可以為空，也可以指向鏈表的任意一個節(jié)點(diǎn)，如果在每生成一個新節(jié)點(diǎn)給其隨機(jī)指針賦值時，都要去遍歷原鏈表的話，OJ 上肯定會超時，所以可以考慮用 HashMap 來縮短查找時間，第一遍遍歷生成所有新節(jié)點(diǎn)時同時建立一個原節(jié)點(diǎn)和新節(jié)點(diǎn)的 HashMap，第二遍給隨機(jī)指針賦值時，查找時間是常數(shù)級。代碼如下：

解法一：

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ù)暮啙?，還是需要一個 HashMap 來建立原鏈表結(jié)點(diǎn)和拷貝鏈表結(jié)點(diǎn)之間的映射。在遞歸函數(shù)中，首先判空，若為空，則返回空指針。然后就是去 HashMap 中查找是否已經(jīng)在拷貝鏈表中存在了該結(jié)點(diǎn)，是的話直接返回。否則新建一個拷貝結(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 占用額外的空間，如果這道題限制了空間的話，就要考慮別的方法。下面這個方法很巧妙，可以分為以下三個步驟：

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

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

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

舉個例子來說吧，比如原鏈表是 1(2) -> 2(3) -> 3(1)，括號中是其 random 指針指向的結(jié)點(diǎn)，那么這個解法是首先比遍歷一遍原鏈表，在每個結(jié)點(diǎn)后拷貝一個同樣的結(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)，所以我們要再加個 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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論