文章目錄

• 題目描述
• 思路 && 代碼
• • • 1. 哈希表法
    • 2. 原地算法
    • 二刷

題目描述

• 主要有兩個考慮點：
  • 不能改變原鏈表
  • 新鏈表賦予 next、random 時，復制結點不一定存在

思路 && 代碼

1. 哈希表法

• O(n)、O(n)
• 參考了dalao的寫法，這里哈希表用得非常巧妙～值得學習！
• 思路：在哈希表中建立 Node - CopyNode 的聯系，在此基礎上進行 next && random 的處理即可。

/* // 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) {if(head == null) {return null;}// 哈希表做法<Node - CopyNode>Map<Node, Node> hashmap = new HashMap<>();for(Node temp = head; temp != null; temp = temp.next) {hashmap.put(temp, new Node(temp.val));}for(Node temp = head; temp != null; temp = temp.next) {// next 的處理hashmap.get(temp).next = hashmap.get(temp.next);// random 的處理hashmap.get(temp).random = hashmap.get(temp.random);}return hashmap.get(head);} }

2. 原地算法

• O(n)、O(1)，相對于方法1，此處不需要占用額外空間～
• 注意：原鏈表的恢復、邊界結點的處理

class Solution {public Node copyRandomList(Node head) {if(head == null) {return null;}// 原地算法// 1. 首先 1 -> 2 -> 3 變成 1 -> 1* -> 2 -> 2* -> 3 -> 3*for(Node temp = head; temp != null; temp = temp.next.next) {Node copy = new Node(temp.val);copy.next = temp.next;temp.next = copy;}// 2. 進行 random 的處理for(Node temp = head; temp != null; temp = temp.next.next) {if(temp.random != null) {temp.next.random = temp.random.next;}}// 3. 分開 1 -> 1* -> 2 -> 2* -> 3 -> 3* 變成 1* -> 2* -> 3*Node copyHead = head.next;for(Node temp = head; temp != null; temp = temp.next) {// 取到原本的正確nextNode nextNode = temp.next.next;// * -> *if(nextNode != null) {temp.next.next = temp.next.next.next;}// 1 -> 2temp.next = nextNode;}return copyHead;} }

二刷

• 哈希表

class Solution {public Node copyRandomList(Node head) {Map<Node, Node> map = new HashMap<>();for(Node temp = head; temp != null; temp = temp.next) {map.put(temp, new Node(temp.val));}for(Node temp = head; temp != null; temp = temp.next) {map.get(temp).next = map.get(temp.next);map.get(temp).random = map.get(temp.random);}return map.get(head);} }

• 原地算法：二刷來看，還是很有含金量的做法思路

class Solution {public Node copyRandomList(Node head) {if(head == null) return null;for(Node temp = head; temp != null; temp = temp.next.next) {Node newNode = new Node(temp.val);newNode.next = temp.next;temp.next = newNode;}for(Node temp = head; temp != null; temp = temp.next.next) {temp.next.random = temp.random == null ? null : temp.random.next;}Node ans = head.next;for(Node temp = head; temp != null; temp = temp.next) {Node tempNode = temp.next;temp.next = temp.next.next;tempNode.next = temp.next == null ? null : tempNode.next.next;}return ans;} }

總結

以上是生活随笔為你收集整理的LeetCode笔记】剑指 Offer 35. 复杂链表的复制（Java、哈希表、原地算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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