一、題目描述

請實現(xiàn) copyRandomList 函數(shù)，復(fù)制一個復(fù)雜鏈表。在復(fù)雜鏈表中，每個節(jié)點(diǎn)除了有一個 next 指針指向下一個節(jié)點(diǎn)，還有一個 random 指針指向鏈表中的任意節(jié)點(diǎn)或者 null。

示例1：

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2：

輸入：head = [[1,1],[2,1]]

輸出：[[1,1],[2,1]]

示例3：

輸入：head = [[3,null],[3,0],[3,null]]

輸出：[[3,null],[3,0],[3,null]]

示例4：

輸入：head = []

輸出：[]解釋：給定的鏈表為空（空指針），因此返回 null。

提示：

-10000 <= Node.val <= 10000

Node.random 為空(null)或指向鏈表中的節(jié)點(diǎn)。

節(jié)點(diǎn)數(shù)目不超過 1000 。

二、思路分析

注：思路分析中的一些內(nèi)容和圖片參考自力扣各位前輩的題解，感謝他們的無私奉獻(xiàn)

分析

復(fù)制普通鏈表：給定鏈表的頭結(jié)點(diǎn)head，復(fù)制普通鏈表很簡單，只需遍歷鏈表，每輪需要：建立新結(jié)點(diǎn) + 讓前驅(qū)結(jié)點(diǎn)的next指向當(dāng)前這個新結(jié)點(diǎn) + 讓當(dāng)前這個新結(jié)點(diǎn)的next指向空

復(fù)制復(fù)雜鏈表：本題鏈表的結(jié)點(diǎn)新增了 random 指針，指向鏈表中的任意結(jié)點(diǎn)或者null。這個 random 指針意味著在復(fù)制過程中，除了構(gòu)建前驅(qū)結(jié)點(diǎn)的next指針，還要構(gòu)建前驅(qū)結(jié)點(diǎn)的ramdom指針。因此，每輪需要：建立2個新結(jié)點(diǎn) + 讓前驅(qū)結(jié)點(diǎn)的next指向第1個新結(jié)點(diǎn) + 讓前驅(qū)結(jié)點(diǎn)的random指向第2個新結(jié)點(diǎn)。但是這有一個問題：并不是每次都需要建立2個新結(jié)點(diǎn)。有時候前驅(qū)結(jié)點(diǎn)的random指向的是已經(jīng)存在的結(jié)點(diǎn)，但是如何判斷出來呢？如果把所有結(jié)點(diǎn)遍歷一遍，那就太麻煩了。

思路

利用哈希表的查詢特點(diǎn)，考慮構(gòu)建原鏈表結(jié)點(diǎn)和新鏈表對應(yīng)結(jié)點(diǎn)的鍵值對映射關(guān)系，再遍歷構(gòu)建新鏈表各結(jié)點(diǎn)的next和random引用指向即可。
 

算法流程：

①若頭節(jié)點(diǎn)head為空結(jié)點(diǎn)，直接返回NULL ；

②初始化：聲明一個哈希表dic，定義一個結(jié)點(diǎn)cur指向頭結(jié)點(diǎn)，這個cur控制后面的循環(huán)

③建立哈希映射：遍歷這個鏈表，每個鏈表結(jié)點(diǎn)對應(yīng)建立一個新結(jié)點(diǎn)，并向dic添加鍵值對(原cur結(jié)點(diǎn), 新cur結(jié)點(diǎn))

④構(gòu)建新鏈表的引用指向：構(gòu)建新結(jié)點(diǎn)的next和random引用指向

⑤返回值： 返回新鏈表的頭結(jié)點(diǎn)，即dic[cur]

三、整體代碼

/*
// 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) {
        //若是空鏈表，則返回NULL
        if(head == NULL) return NULL;
        //創(chuàng)建一個結(jié)點(diǎn)，指向這個鏈表的頭結(jié)點(diǎn)。這個結(jié)點(diǎn)用來控制后面的循環(huán)
        Node* cur = head; 
        //創(chuàng)建一個哈希表
        unordered_map<Node*, Node*> map;
        while(cur != NULL){
            //為鏈表每個結(jié)點(diǎn)創(chuàng)建一個對應(yīng)的新結(jié)點(diǎn)，并建立原結(jié)點(diǎn)和新結(jié)點(diǎn)的Map映射
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        //為新鏈表每個結(jié)點(diǎn)的next和random設(shè)置對應(yīng)的指向
        while(cur != NULL){
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        //返回新鏈表的頭結(jié)點(diǎn)
        return map[head];
    }
};

總結(jié)

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!     

最新評論