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。
題目來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
2.解法
2.1 拼接+拆分
首先我們逐個(gè)將節(jié)點(diǎn)復(fù)制并且和原來(lái)的鏈表連起來(lái)得新鏈表；
然后再構(gòu)建新鏈表的random 指向。當(dāng)訪問(wèn)原節(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)拆分出來(lái)連成一個(gè)復(fù)制鏈表，拆分成原鏈表和復(fù)制鏈表。
鏈表圖
復(fù)制節(jié)點(diǎn)
將復(fù)制節(jié)點(diǎn)的random.next 連接起來(lái)
拆分成兩個(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計(jì)算黑洞數(shù)的方法,簡(jiǎn)單描述了黑洞數(shù)的概念及具體計(jì)算方法,涉及java數(shù)值運(yùn)算相關(guān)操作技巧,需要的朋友可以參考下2017-12-12
Mybatis實(shí)現(xiàn)Mapper動(dòng)態(tài)代理方式詳解
這篇文章主要為大家詳細(xì)介紹了Mybatis實(shí)現(xiàn)Mapper動(dòng)態(tài)代理方式，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-08-08
Spring Boot使用一個(gè)application.properties或者application.yaml的文件作為全局配置文件，本文重點(diǎn)給大家介紹Spring Boot兩種全局配置和兩種注解的配置方法，感興趣的朋友一起看看吧2021-06-06
鄰接表無(wú)向圖的Java語(yǔ)言實(shí)現(xiàn)完整源碼
這篇文章主要介紹了鄰接表無(wú)向圖的Java語(yǔ)言實(shí)現(xiàn)完整源碼，具有一定借鑒價(jià)值，需要的朋友可以參考下。2017-12-12
spring中WebClient如何設(shè)置連接超時(shí)時(shí)間以及讀取超時(shí)時(shí)間
這篇文章主要給大家介紹了關(guān)于spring中WebClient如何設(shè)置連接超時(shí)時(shí)間以及讀取超時(shí)時(shí)間的相關(guān)資料,WebClient是Spring框架5.0引入的基于響應(yīng)式編程模型的HTTP客戶端,它提供一種簡(jiǎn)便的方式來(lái)處理HTTP請(qǐng)求和響應(yīng),需要的朋友可以參考下2024-08-08
這篇文章主要介紹了Java中Mybatis分頁(yè)查詢的四種傳參方式：順序傳參，@param傳參，自定義POJO類傳參，Map傳參，想詳細(xì)了解傳參方式的小伙伴可以詳細(xì)閱讀本文，有一定的而參考價(jià)值2023-03-03
目前使用的主流版本還是JDK 8,但偶爾會(huì)想體驗(yàn)下新版本(或者舊版本),如果能裝多個(gè)版本的JDK,而且很方便的切換就好了,這篇文章主要給大家介紹了關(guān)于Mac電腦安裝多個(gè)JDK版本的相關(guān)資料,需要的朋友可以參考下2024-03-03
淺談@RequestBody和@RequestParam可以同時(shí)使用
這篇文章主要介紹了@RequestBody和@RequestParam可以同時(shí)使用，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-03-03
Tomcat正常啟動(dòng),訪問(wèn)所有頁(yè)面均報(bào)404異常,404異?？偨Y(jié)分析
今天遇到一個(gè)問(wèn)題：Tomcat正常啟動(dòng)，訪問(wèn)所有頁(yè)面均報(bào)404異常,究竟該如何解決這個(gè)問(wèn)題呢？下邊小編將為大家介紹一下解決方法，需要的朋友可以參考下2013-07-07
使用Spring事物時(shí)不生效的場(chǎng)景及解決方法
今天介紹一下Spring事物不生效的場(chǎng)景,事物是我們?cè)陧?xiàng)目中經(jīng)常使用的,如果是Java的話,基本上都使用Spring的事物,不過(guò)Spring的事物如果使用不當(dāng),那么就會(huì)導(dǎo)致事物失效或者不回滾,最終導(dǎo)致數(shù)據(jù)不一致,下面我們意義列舉不生效的場(chǎng)景,并給出解決方法2023-09-09