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