一、題目描述

請實(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。

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

二、運(yùn)行結(jié)果

三、解題思路

復(fù)制復(fù)雜鏈表的難點(diǎn)在于random指針的復(fù)制，這里使用一個(gè)哈希表來保存每一個(gè)院鏈表中的結(jié)點(diǎn)與對應(yīng)的新鏈表中的結(jié)點(diǎn)之間的對應(yīng)關(guān)系，在第一次遍歷原鏈表進(jìn)行復(fù)制的時(shí)候，先不處理每個(gè)新鏈表結(jié)點(diǎn)的random指針，只是保存新舊結(jié)點(diǎn)之間的對應(yīng)關(guān)系。

簡單對原鏈表復(fù)制完成之后（沒有處理random指針），所有的結(jié)點(diǎn)都已經(jīng)復(fù)制完成，在重頭遍歷一次鏈表，處理random指針，而random指針可以根據(jù)先前保存的對應(yīng)關(guān)系進(jìn)行設(shè)置，根據(jù)原鏈表中每個(gè)結(jié)點(diǎn)的random指針設(shè)置新鏈表中每個(gè)結(jié)點(diǎn)的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<>(); //原結(jié)點(diǎn)和新結(jié)點(diǎn)之間的映射關(guān)系Node dummy = new Node(-1);if(head == null) return null;Node tmpNode = new Node(p.val);        //指向新構(gòu)建的結(jié)點(diǎn)dummy.next = tmpNode;   Node rear = tmpNode;     //指向新構(gòu)建鏈表的末尾結(jié)點(diǎn)map.put(head, tmpNode);while(p.next != null){   //先復(fù)制每個(gè)結(jié)點(diǎn)和next指針，先不管random指針Node pnext = p.next;tmpNode = new Node(pnext.val);rear.next = tmpNode; // 指針后移rear = tmpNode;p = pnext;map.put(pnext, tmpNode); // 保存映射關(guān)系}p = head;          // 再重頭到尾掃描一遍鏈表tmpNode = dummy.next;while(p != null){  //構(gòu)建random指針tmpNode.random = map.get(p.random);p = p.next;tmpNode = tmpNode.next;}return dummy.next;}
}