Java關(guān)于重排鏈表詳細解析
更新時間：2022年01月25日 14:51:16 作者：Fly upward
在我們平時的代碼過程中，鏈表是我們經(jīng)常遇到的一個數(shù)據(jù)結(jié)構(gòu)，面試題中鏈表占很大一部分，可見鏈表操作是非常重要的。本篇文章我們來探究一下如何進行重排鏈表
1.題目
給定一個單鏈表 L 的頭節(jié)點 head ，單鏈表 L 表示為：
?L0→ L1?→ … → Ln-1?→ Ln? 請將其重新排列后變?yōu)椋?/p>
L0?→?Ln?→?L1?→?Ln-1?→?L2?→?Ln-2?→ …
不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際的進行節(jié)點交換。
?來源：力扣（LeetCode）
2.解析
將一個鏈表分為兩個子鏈表，然后將其歸并。
我們要先找到鏈表的中間節(jié)點，在中間節(jié)點將其斷開
然后反轉(zhuǎn)后半鏈表
再將兩個子鏈表逐個連起來
?將后半鏈表反轉(zhuǎn)，獨立成一個子鏈表。
最后將兩個子鏈表的節(jié)點逐個連接就OK了
3.代碼
class Solution {
public void reorderList(ListNode head) {
ListNode fast = head;
ListNode slow = head;
//找中間節(jié)點
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//截斷鏈表
ListNode cur = slow.next;
slow.next = null;
//反轉(zhuǎn)后半鏈表
ListNode node = null;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = node;
node = cur;
cur = curNext;
}
//合并
ListNode prev = head;
ListNode l1 = node;
while (l1 != null) {
ListNode next1 = prev.next;
ListNode next2 = l1.next;
prev.next = l1;
l1.next = next1;
prev = next1;
l1 = next2;
}
}
}
到此這篇關(guān)于Java關(guān)于重排鏈表詳細解析的文章就介紹到這了,更多相關(guān)Java 重排鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Java通過IO流輸出文件目錄，本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-12-12
關(guān)于JAVA經(jīng)典算法40題(超實用版)
本篇文章小編為大家介紹一下，關(guān)于JAVA經(jīng)典算法40題(超實用版)，有需要的朋友可以參考一下2013-04-04
這篇文章主要介紹了Java自定義實現(xiàn)equals()方法過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-02-02
SpringMVC Controller解析ajax參數(shù)過程詳解
這篇文章主要介紹了SpringMVC Controller解析ajax參數(shù)過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-07-07
這篇文章主要介紹了Jlabel實現(xiàn)內(nèi)容自動換行簡單實例，具有一定借鑒價值,需要的朋友可以參考下2018-01-01
這篇文章主要介紹了SpringMVC上傳文件并保存到本地代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-11-11
idea根據(jù)實體類生成數(shù)據(jù)庫表的流程步驟
在開發(fā)的時候,經(jīng)常會遇到數(shù)據(jù)庫表結(jié)構(gòu)設(shè)計無法滿足業(yè)務(wù)的需求,需要去改動數(shù)據(jù)庫表,我們就需要去設(shè)計數(shù)據(jù)庫的字段,然后又回來增加實體類里的字段,這樣很麻煩,所以本文給大家介紹了idea根據(jù)實體類生成數(shù)據(jù)庫表的流程步驟,需要的朋友可以參考下2024-12-12
這篇文章主要介紹了Spring Security中防護CSRF功能，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-01-01
這篇文章主要介紹了一下Java中的堆和棧,Java數(shù)據(jù)類型在執(zhí)行過程中存儲在兩種不同形式的內(nèi)存中：棧和堆，它們通常由運行Java虛擬機(JVM)的底層平臺維護,需要的朋友可以參考下2023-04-04
SpringBoot去除內(nèi)嵌tomcat的實現(xiàn)
這篇文章主要介紹了SpringBoot去除內(nèi)嵌tomcat的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-09-09