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

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

[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.

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

解法一：

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

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

解法二：

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

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

1. 在原鏈表的每個節點后面拷貝出一個新的節點。

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

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

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

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

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

解法二：

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

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