目錄
1.題目
2.解法
2.1 拼接+拆分
3.代碼
1.題目
請實作 copyRandomList 函式，復制一個復雜鏈表，在復雜鏈表中，每個節點除了有一個 next 指標指向下一個節點，還有一個 random 指標指向鏈表中的任意節點或者 null，
題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
2.解法
2.1 拼接+拆分
首先我們逐個將節點復制并且和原來的鏈表連起來得新鏈表；
然后再構建新鏈表的random 指向，當訪問原節點 cur 的隨機指向節點 cur.random 時，對應新節點 cur.next 的隨機指向節點為 cur.random.next
將得到的新鏈表之間的復制節點拆分出來連成一個復制鏈表，拆分成原鏈表和復制鏈表，
鏈表圖
復制節點
將復制節點的random.next 連接起來
拆分成兩個鏈表
3.代碼
class Solution {
public Node copyRandomList(Node head) {
if(head == null) {
return null;
}
//1.復制各個鏈表，并連接
Node cur = head;
while (cur != null) {
//復制
Node prev = new Node(cur.val);
prev.next = cur.next;
//連接
cur.next = prev;
//往后走
cur = prev.next;
}
//2.構建各新節點的random 指向
cur = head;
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
//3.拆分復制的鏈表
cur = head.next;
Node node = head;
Node nodeNext = head.next;
while (cur.next != null) {
node.next = node.next.next;
cur.next = cur.next.next;
node = node.next;
cur = cur.next;
}
node.next = null;//尾節點
return nodeNext;//回傳新鏈表的頭結點
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/393127.html
標籤：java
上一篇：LeetCode - 92 - 反轉鏈表|| - java - 兩種解法 - 細喔~
下一篇：MyBatis筆記