Java復(fù)雜鏈表的復(fù)制詳解
1.題目
請(qǐng)實(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。
題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
2.解法
2.1 拼接+拆分
首先我們逐個(gè)將節(jié)點(diǎn)復(fù)制并且和原來的鏈表連起來得新鏈表；
然后再構(gòu)建新鏈表的random 指向。當(dāng)訪問原節(jié)點(diǎn) cur 的隨機(jī)指向節(jié)點(diǎn) cur.random 時(shí)，對(duì)應(yīng)新節(jié)點(diǎn) cur.next 的隨機(jī)指向節(jié)點(diǎn)為 cur.random.next
將得到的新鏈表之間的復(fù)制節(jié)點(diǎn)拆分出來連成一個(gè)復(fù)制鏈表，拆分成原鏈表和復(fù)制鏈表。
鏈表圖
復(fù)制節(jié)點(diǎn)
將復(fù)制節(jié)點(diǎn)的random.next 連接起來
拆分成兩個(gè)鏈表
3.代碼
class Solution {
public Node copyRandomList(Node head) {
if(head == null) {
return null;
}
//1.復(fù)制各個(gè)鏈表，并連接
Node cur = head;
while (cur != null) {
//復(fù)制
Node prev = new Node(cur.val);
prev.next = cur.next;
//連接
cur.next = prev;
//往后走
cur = prev.next;
}
//2.構(gòu)建各新節(jié)點(diǎn)的random 指向
cur = head;
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
//3.拆分復(fù)制的鏈表
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;//尾節(jié)點(diǎn)
return nodeNext;//返回新鏈表的頭結(jié)點(diǎn)
}
}
到此這篇關(guān)于Java復(fù)雜鏈表的復(fù)制詳解的文章就介紹到這了,更多相關(guān)Java 復(fù)雜鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Java在PDF中添加表格過程詳解，本文將介紹通過Java編程在PDF文檔中添加表格的方法。添加表格時(shí)，可設(shè)置表格邊框、單元格對(duì)齊方式、單元格背景色、單元格合并、插入圖片、設(shè)置行高、列寬、字體、字號(hào)等,需要的朋友可以參考下2019-07-07
mybatis插入數(shù)據(jù)后如何返回新增數(shù)據(jù)的id值
當(dāng)往mysql數(shù)據(jù)庫插入一條數(shù)據(jù)時(shí),有時(shí)候需要知道剛插入的信息,下面這篇文章主要給大家介紹了關(guān)于mybatis插入數(shù)據(jù)后如何返回新增數(shù)據(jù)id值的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06
關(guān)于Java8的foreach中使用return/break/continue產(chǎn)生的問題
這篇文章主要介紹了關(guān)于Java8的foreach()中使用return/break/continue產(chǎn)生的問題,在使用foreach()處理集合時(shí)不能使用break和continue這兩個(gè)方法,也就是說不能按照普通的for循環(huán)遍歷集合時(shí)那樣根據(jù)條件來中止遍歷,需要的朋友可以參考下2023-10-10
Java中線程的等待與喚醒_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
在Object.java中，定義了wait(), notify()和notifyAll()等接口。wait()的作用是讓當(dāng)前線程進(jìn)入等待狀態(tài)，同時(shí)，wait()也會(huì)讓當(dāng)前線程釋放它所持有的鎖。下面通過本文給大家介紹Java中線程的等待與喚醒知識(shí)，感興趣的朋友一起看看吧2017-05-05
解決java轉(zhuǎn)義json出現(xiàn)\u0000 等亂碼的問題
這篇文章主要介紹了解決java轉(zhuǎn)義json出現(xiàn)\u0000 等亂碼的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2021-03-03
mybatis 獲取無數(shù)據(jù)的字段不顯示的問題
這篇文章主要介紹了mybatis 獲取無數(shù)據(jù)的字段不顯示的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07
Java基本概念監(jiān)視器實(shí)習(xí)原理解析
這篇文章主要介紹了Java基本概念監(jiān)視器實(shí)習(xí)原理解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08
RocketMQ消息隊(duì)列實(shí)現(xiàn)隨機(jī)消息發(fā)送當(dāng)做七夕禮物
這篇文章主要為大家介紹了RocketMQ消息隊(duì)列實(shí)現(xiàn)隨機(jī)消息發(fā)送當(dāng)做七夕禮物，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-08-08
Java微信公眾平臺(tái)開發(fā)（11） 微信三大平臺(tái)的關(guān)聯(lián)
這篇文章主要介紹了Java微信公眾平臺(tái)開發(fā)第十一步，微信開發(fā)中微信公眾平臺(tái)、開放平臺(tái)和商戶平臺(tái)的關(guān)聯(lián)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-04-04
這篇文章主要介紹了Mybatis ResultType如何處理返回類型方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-01-01