題目描述

輸入一個復雜鏈表（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），返回結果為復制鏈表的head。（注意，輸出結果中請不要返回參數中的節點引用，否則判斷程序會直接返回空）

兩種策略解決

策略1（HashMap解決）

先用一個HashMap的key存放原來的鏈表，value存放key的值。

知道了key的指向，然后讓value跟著key一樣的指向即可。

代碼

import java.util.HashMap;/*** @author god-jiang* @date 2020/1/16 18:48*/ public class RandomListNodeCopy {//定義復雜鏈表的結構public class RandomListNode {int label;RandomListNode next = null;RandomListNode random = null;RandomListNode(int label) {this.label = label;}}public RandomListNode Clone(RandomListNode pHead) {HashMap<RandomListNode, RandomListNode> map = new HashMap<>();RandomListNode cur = pHead;while (cur != null) {map.put(cur, new RandomListNode(cur.label));cur = cur.next;}cur = pHead;while (cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}return map.get(pHead);} }

通過截圖

HashMap解法總結

用HashMap做簡單，容易理解，時間復雜度為O(N)，空間復雜度也為O(N)，其實這道題還可以做到時間復雜度為O(N)，空間復雜度為O(1)，就是我接下來介紹的這種解法。

---

策略2（創建拆分）

遍歷鏈表，復制每個節點，如復制節點A得到A1，將節點A1插到節點A后面

重新遍歷鏈表，復制舊節點的隨機指針給新節點，如A1.random = A.random.next

拆分鏈表，將鏈表拆分為原鏈表和復制后的鏈表

圖解

代碼

import java.util.HashMap;/*** @author god-jiang* @date 2020/1/16 18:48*/ public class RandomListNodeCopy {//定義復雜鏈表的結構public class RandomListNode {int label;RandomListNode next = null;RandomListNode random = null;RandomListNode(int label) {this.label = label;}}//合并拆分的時間復雜度為O(N)，空間復雜度為O(1)public RandomListNode Clone(RandomListNode pHead) {if (pHead == null) {return null;}RandomListNode cur = pHead;//1、復制每個結點，如復制結點A得到A1，將結點A1插到結點A后面；while (cur != null) {RandomListNode cloneNode = new RandomListNode(cur.label);RandomListNode nextNode = cur.next;cur.next = cloneNode;cloneNode.next = nextNode;cur = nextNode;}cur = pHead;//2、重新遍歷鏈表，復制老結點的隨機指針給新結點，如A1.random = A.random.next;while (cur != null) {cur.next.random = cur.random == null ? null : cur.random.next;cur = cur.next.next;}//3、拆分鏈表，將鏈表拆分為原鏈表和復制后的鏈表cur = pHead;RandomListNode pCloneHead = pHead.next;while (cur != null) {RandomListNode cloneNode = cur.next;cur.next = cloneNode.next;cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next;cur = cur.next;}return pCloneHead;} }

通過截圖

總結

一道好的題目往往有多種解決的辦法，大二時期的我就只會用最基礎的貪心和暴力解決各類問題，不是說暴力解法不好，只是有時候有更好的算法可以解決我們又為何不去掌握呢。所以一道題目的多種的解法我都會好好研讀和學習。希望也有人喜歡和我一樣多了解多種解法，擴展一下自己的思路，嘿嘿嘿。。。

PS：如果覺得博主寫的不錯的話可以點點贊，關注走一波，謝謝大家的支持了~~~

總結

以上是生活随笔為你收集整理的hashmap 复制_复杂链表的复制的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。