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

復制鏈表的復制

“題目描述 ：請實現 copyRandomList 函數，復制一個復雜鏈表。在復雜鏈表中，每個節點除了有一個 next 指針指向下一個節點，還有一個 random 指針指向鏈表中的任意節點或者 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)或指向鏈表中的節點。
• 節點數目不超過 1000 。

方法：哈希表

“利用哈希表的查詢特點，考慮構建原鏈表節點和新鏈表對應節點的鍵值對映射關系,再遍歷構建新鏈表各節點的next 和random 引用指向即可。

算法流程:

• 若頭節點head為空節點，直接返回null ;
• 初始化:哈希表dic ，節點cur 指向頭節點;
• 復制鏈表:
  • 建立新節點，并向dic添加鍵值對(原cur節點，新cur節點) ;
  • cur 遍歷至原鏈表下一節點;
• 構建新鏈表的引用指向:
  • 構建新節點的next 和random 弓|用指向;
  • cur 遍歷至原鏈表下一節點;
• 返回值:新鏈表的頭節點dic[cur] ;

復雜度分析:

• 時間復雜度O(N) ：兩輪遍歷鏈表，使用O(N)時間。
• 空間復雜度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 
 * @微信公眾號 程序員千羽 
 * @個人網站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description:  復雜鏈表的復制 
 */ 
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. 復制各節點，并建立 “原節點 -> 新節點” 的 Map 映射 
        while(cur != null) { 
            map.put(cur, new Node(cur.val)); 
            cur = cur.next; 
        } 
        cur = head; 
        // 4. 構建新鏈表的 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. 返回新鏈表的頭節點 
        return map.get(head); 
    } 
 
 
    /** 
     * 思路：先復制鏈表的 next 節點，將復制后的節點接在原節點后，然后復制其它的 
     * 節點，最后取偶數位置的節點（復制后的節點）。 
     * 
     * @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-