C++中怎么利用LeetCode拷貝帶有隨機指針的鏈表

這篇文章將為大家詳細講解有關(guān)C++中怎么利用LeetCode拷貝帶有隨機指針的鏈表，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

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

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.

這道鏈表的深度拷貝題的難點就在于如何處理隨機指針的問題，由于每一個節(jié)點都有一個隨機指針，這個指針可以為空，也可以指向鏈表的任意一個節(jié)點，如果在每生成一個新節(jié)點給其隨機指針賦值時，都要去遍歷原鏈表的話，OJ 上肯定會超時，所以可以考慮用 HashMap 來縮短查找時間，第一遍遍歷生成所有新節(jié)點時同時建立一個原節(jié)點和新節(jié)點的 HashMap，第二遍給隨機指針賦值時，查找時間是常數(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é)點和拷貝鏈表結(jié)點之間的映射。在遞歸函數(shù)中，首先判空，若為空，則返回空指針。然后就是去 HashMap 中查找是否已經(jīng)在拷貝鏈表中存在了該結(jié)點，是的話直接返回。否則新建一個拷貝結(jié)點 res，然后建立原結(jié)點和該拷貝結(jié)點之間的映射，然后就是要給拷貝結(jié)點的 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é)點后面拷貝出一個新的節(jié)點。

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

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

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

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

這里的 cur 是原鏈表中結(jié)點，cur->next 則為拷貝鏈表的結(jié)點，cur->next->random 則為拷貝鏈表的 random 指針。cur->random 為原鏈表結(jié)點的 random 指針指向的結(jié)點，因為其指向的還是原鏈表的結(jié)點，所以我們要再加個 next，才能指向拷貝鏈表的結(jié)點。最后再遍歷一次，就是要把原鏈表和拷貝鏈表斷開即可，參見代碼如下：

解法二：

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;
    }
};

關(guān)于C++中怎么利用LeetCode拷貝帶有隨機指針的鏈表就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。