[[438684]]

Leetcode : https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_28_copyRandomList/Solution.java

復(fù)制鏈表的復(fù)制

“題目描述 ：請(qǐng)實(shí)現(xiàn) copyRandomList 函數(shù)，復(fù)制一個(gè)復(fù)雜鏈表。在復(fù)雜鏈表中，每個(gè)節(jié)點(diǎn)除了有一個(gè) next 指針指向下一個(gè)節(jié)點(diǎn)，還有一個(gè) 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 。

方法：哈希表

“利用哈希表的查詢特點(diǎn)，考慮構(gòu)建原鏈表節(jié)點(diǎn)和新鏈表對(duì)應(yīng)節(jié)點(diǎn)的鍵值對(duì)映射關(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);
• 復(fù)制鏈表:
  • 建立新節(jié)點(diǎn)，并向dic添加鍵值對(duì)(原cur節(jié)點(diǎn)，新cur節(jié)點(diǎn)) ;
  • cur 遍歷至原鏈表下一節(jié)點(diǎn);
• 構(gòu)建新鏈表的引用指向:
  • 構(gòu)建新節(jié)點(diǎn)的next 和random 弓|用指向;
  • cur 遍歷至原鏈表下一節(jié)點(diǎn);
• 返回值:新鏈表的頭節(jié)點(diǎn)dic[cur] ;

復(fù)雜度分析:

• 時(shí)間復(fù)雜度O(N) ：兩輪遍歷鏈表，使用O(N)時(shí)間。
• 空間復(fù)雜度0(N) ：哈希表dic 使用線性大小的額外空間。

package com.nateshao.sword_offer.topic_28_copyRandomList; 
 
import java.util.HashMap; 
import java.util.Map; 
 
/** 
 * @date Created by 邵桐杰 on 2021/12/2 14:05 
 * @微信公眾號(hào) 程序員千羽 
 * @個(gè)人網(wǎng)站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description:  復(fù)雜鏈表的復(fù)制 
 */ 
public class Solution { 
    /** 
     * 精選解答 
     * @param head 
     * @return 
     */ 
    public Node copyRandomList(Node head) { 
        if(head == null) return null; 
        Node cur = head; 
        Map<Node, Node> map = new HashMap<>(); 
        // 3. 復(fù)制各節(jié)點(diǎn)，并建立 “原節(jié)點(diǎn) -> 新節(jié)點(diǎn)” 的 Map 映射 
        while(cur != null) { 
            map.put(cur, new Node(cur.val)); 
            cur = cur.next; 
        } 
        cur = head; 
        // 4. 構(gòu)建新鏈表的 next 和 random 指向 
        while(cur != null) { 
            map.get(cur).next = map.get(cur.next); 
            map.get(cur).random = map.get(cur.random); 
            cur = cur.next; 
        } 
        // 5. 返回新鏈表的頭節(jié)點(diǎn) 
        return map.get(head); 
    } 
 
 
    /** 
     * 思路：先復(fù)制鏈表的 next 節(jié)點(diǎn)，將復(fù)制后的節(jié)點(diǎn)接在原節(jié)點(diǎn)后，然后復(fù)制其它的 
     * 節(jié)點(diǎn)，最后取偶數(shù)位置的節(jié)點(diǎn)（復(fù)制后的節(jié)點(diǎn)）。 
     * 
     * @param head 
     * @return 
     */ 
    public Node copyRandomList2(Node head) { 
        if (head == null) return null; 
        Node node = new Node(head.val); 
        Node temp = node; 
 
        while (head.next != null) { 
            temp.next = new Node(head.next.val); 
            if (head.random != null) { 
                temp.random = new Node(head.random.val); 
            } 
            head = head.next; 
            temp = temp.next; 
        } 
        return head; 
    } 
 
    // Definition for a Node. 
    class Node { 
        int val; 
        Node next; 
        Node random; 
 
        public Node(int val) { 
            this.val = val; 
            this.next = null; 
            this.random = null; 
        } 
    } 
} 

參考鏈接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-