題目

解題核心思路：找random指針指向

這里的拷貝屬于深拷貝，就是不光是拷貝值，還要拷貝其指針的引用情況。如果只是單獨(dú)的單向鏈表，則直接可以根據(jù)next指向找到下一個(gè)結(jié)點(diǎn)，然后創(chuàng)建一個(gè)新節(jié)點(diǎn)復(fù)制過(guò)來(lái)，直接拷貝，但是題目中的random指針指向的節(jié)點(diǎn)是沒(méi)有歸類的，這樣我們就不可能使用普通的循環(huán)來(lái)進(jìn)行拷貝，因?yàn)樵诳截惖臅r(shí)候，你只能找到next，但是random并不知道，可能拷貝的同時(shí)random都還沒(méi)創(chuàng)建出來(lái)

思路一：哈希

此題的復(fù)制，不單單要復(fù)制本身的.val值，還要把其next和random指向給復(fù)制過(guò)來(lái)。
那么我們可以借助一個(gè)哈希表Map來(lái)記錄下舊鏈表的映射關(guān)系，key為舊鏈表的節(jié)點(diǎn)（包含next和random指向），value為新建的新節(jié)點(diǎn)（val值直接copy舊鏈表的節(jié)點(diǎn)）

1. 建立哈希表，key為舊鏈表的節(jié)點(diǎn)，value為新建的新節(jié)點(diǎn)
2. 然后去循環(huán)鏈表的同時(shí)，根據(jù)key取出新節(jié)點(diǎn)，并且（依據(jù)舊節(jié)點(diǎn)）設(shè)置新節(jié)點(diǎn)的next和random
3. 最后返回新鏈表的首節(jié)點(diǎn)map.get(head);
   

這里可以用純哈希+while或者 哈希+遞歸的方法，原理都是一樣的

思路二：迭代構(gòu)造新鏈表

給每個(gè)舊鏈表節(jié)點(diǎn)后面都連上一個(gè)自己的復(fù)制節(jié)點(diǎn)，然后再根據(jù)老節(jié)點(diǎn)的random給后面的新節(jié)點(diǎn)附上，最后在把就新鏈表拆出來(lái)

1. 構(gòu)建新老鏈表結(jié)合體
   

2. 更新新節(jié)點(diǎn)的random
   

3. 拆鏈
   文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-684129.html

方法一：哈希+遞歸

 方法一 : 遞歸+哈希---->用哈希表記錄舊值和新值的映射，讓新值根據(jù)舊值的連接關(guān)系，構(gòu)建新鏈表
    Map<Node, Node> map = new HashMap<Node, Node>();
    public Node copyRandomList(Node head) {
        if(head==null) return null;

        if(!map.containsKey(head)){//如果map集合不含head  則創(chuàng)建一份新的head進(jìn)去  
         Node newHead = new Node(head.val);
         map.put(head,newHead);//key--->舊值  value--->新值   
         //給新值附上 next 和random
         newHead.next = copyRandomList(head.next);
         newHead.random = copyRandomList(head.random);
        }
        return map.get(head);
    }

方法二：純哈希

方法二： 純哈希----->  使用hash存儲(chǔ)原結(jié)點(diǎn)和克隆結(jié)點(diǎn)的映射關(guān)系，通過(guò)映射關(guān)系處理克隆結(jié)點(diǎn)的random指針
    public Node copyRandomList(Node head) {
        if(head==null) return head;

        // map方法，空間復(fù)雜度O(n)
        Node oldNode = head;
       // 使用hash表存儲(chǔ)舊結(jié)點(diǎn)和新結(jié)點(diǎn)的映射
        Map<Node,Node> map = new HashMap<>();
        while(oldNode != null){
            Node newNode = new Node(oldNode.val);
            map.put(oldNode,newNode);
            oldNode = oldNode.next;
        }

        oldNode = head;//重置 oldNode 位置到head頭結(jié)點(diǎn)
        while(oldNode != null){ //根據(jù)舊node 映射新node
        map.get(oldNode).next = map.get(oldNode.next);
        map.get(oldNode).random = map.get(oldNode.random);
        oldNode = oldNode.next;
        }
        return map.get(head);//返回頭結(jié)點(diǎn)的映射新節(jié)點(diǎn)
    }

方法三：迭代 + 節(jié)點(diǎn)拆分

/ 方法三： 迭代 + 節(jié)點(diǎn)拆分---->  給每一個(gè)舊的鏈表節(jié)點(diǎn)去拼接一個(gè)新的到舊節(jié)點(diǎn)后面，然后將新結(jié)點(diǎn)的random指向舊節(jié)點(diǎn)的random指向，最后再把新的節(jié)點(diǎn)拆分出來(lái)
public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // for (Node node = head; node != null; node = node.next.next) {
        //     Node nodeNew = new Node(node.val);
        //     nodeNew.next = node.next;
        //     node.next = nodeNew;
        // }
        // 第一次遍歷，拼接新舊鏈表 舊1-->新1-->舊2--->新2
        Node node = head;
        while(node != null){
             Node nodeNew = new Node(node.val);
             nodeNew.next = node.next;
             node.next = nodeNew;
             node = node.next.next;
        }
        // for (Node node = head; node != null; node = node.next.next) {
        //     Node nodeNew = node.next;
        //     if(node.random != null) nodeNew.random = node.random.next;
        //     else nodeNew.random = null;
        // }
        // 第二次遍歷，給新結(jié)點(diǎn)連上舊節(jié)點(diǎn)的random
         node = head;// 重置node到head位置
        while(node != null){
            Node nodeNew = node.next;
            if(node.random != null) nodeNew.random = node.random.next; 
            //如果舊節(jié)點(diǎn)的random指向null  null本身沒(méi)有新節(jié)點(diǎn)，則直接讓新節(jié)點(diǎn)的random指向null
            else nodeNew.random = null;
            node = node.next.next;
        }

        Node headNew = head.next;
        // for (Node node = head; node != null; node = node.next) {
        //     Node nodeNew = node.next;
        //     node.next = node.next.next;
        //     if(nodeNew.next != null) nodeNew.next = nodeNew.next.next;
        //     else nodeNew.next = null;
        // }
        node = head;// 重置node到head位置
        // 第三次遍歷，拆分新鏈表出來(lái)
        while(node != null){
            Node nodeNew = node.next;
            node.next = nodeNew.next;
            if(nodeNew.next != null) nodeNew.next = nodeNew.next.next;
            else nodeNew.next = null;//防止最后一個(gè)新鏈表nodeNew.next.next出現(xiàn)空指針
            node = node.next;
        }
        return headNew;
    }

到了這里，關(guān)于【LeetCode-中等題】138. 復(fù)制帶隨機(jī)指針的鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！