一、題目描述

請實現(xiàn) copyRandomList 函數(shù)，復制一個復雜鏈表。在復雜鏈表中，每個節(jié)點除了有一個 next 指針指向下一個節(jié)點，還有一個 random 指針指向鏈表中的任意節(jié)點或者 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。

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作權歸領扣網絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

二、運行結果

三、解題思路

復制復雜鏈表的難點在于random指針的復制，這里使用一個哈希表來保存每一個院鏈表中的結點與對應的新鏈表中的結點之間的對應關系，在第一次遍歷原鏈表進行復制的時候，先不處理每個新鏈表結點的random指針，只是保存新舊結點之間的對應關系。

簡單對原鏈表復制完成之后（沒有處理random指針），所有的結點都已經復制完成，在重頭遍歷一次鏈表，處理random指針，而random指針可以根據(jù)先前保存的對應關系進行設置，根據(jù)原鏈表中每個結點的random指針設置新鏈表中每個結點的random指針。

四、AC代碼

/*
// 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;}
}
*/
class Solution {public Node copyRandomList(Node head) {Node p = head;           // 工作指針，遍歷原鏈表Map<Node, Node> map = new HashMap<>(); //原結點和新結點之間的映射關系Node dummy = new Node(-1);if(head == null) return null;Node tmpNode = new Node(p.val);        //指向新構建的結點dummy.next = tmpNode;   Node rear = tmpNode;     //指向新構建鏈表的末尾結點map.put(head, tmpNode);while(p.next != null){   //先復制每個結點和next指針，先不管random指針Node pnext = p.next;tmpNode = new Node(pnext.val);rear.next = tmpNode; // 指針后移rear = tmpNode;p = pnext;map.put(pnext, tmpNode); // 保存映射關系}p = head;          // 再重頭到尾掃描一遍鏈表tmpNode = dummy.next;while(p != null){  //構建random指針tmpNode.random = map.get(p.random);p = p.next;tmpNode = tmpNode.next;}return dummy.next;}
}