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