Java關(guān)于重排鏈表詳細(xì)解析

更新時(shí)間：2022年01月25日 14:51:16 作者：Fly upward

在我們平時(shí)的代碼過程中，鏈表是我們經(jīng)常遇到的一個(gè)數(shù)據(jù)結(jié)構(gòu)，面試題中鏈表占很大一部分，可見鏈表操作是非常重要的。本篇文章我們來探究一下如何進(jìn)行重排鏈表

1.題目

給定一個(gè)單鏈表 L 的頭節(jié)點(diǎn) head ，單鏈表 L 表示為：

?L0→ L1?→ … → Ln-1?→ Ln? 請將其重新排列后變?yōu)椋?/p>

L0?→?Ln?→?L1?→?Ln-1?→?L2?→?Ln-2?→ …

不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

?來源：力扣（LeetCode）

2.解析

將一個(gè)鏈表分為兩個(gè)子鏈表，然后將其歸并。

我們要先找到鏈表的中間節(jié)點(diǎn)，在中間節(jié)點(diǎn)將其斷開

然后反轉(zhuǎn)后半鏈表

再將兩個(gè)子鏈表逐個(gè)連起來

?將后半鏈表反轉(zhuǎn)，獨(dú)立成一個(gè)子鏈表。

最后將兩個(gè)子鏈表的節(jié)點(diǎn)逐個(gè)連接就OK了

3.代碼

class Solution {
    public void reorderList(ListNode head) {
        
        ListNode fast = head;
        ListNode slow = head;
        //找中間節(jié)點(diǎn)
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //截?cái)噫湵?
        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)于重排鏈表詳細(xì)解析的文章就介紹到這了,更多相關(guān)Java 重排鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

相關(guān)文章

Java通過IO流輸出文件目錄的實(shí)例代碼
這篇文章主要介紹了Java通過IO流輸出文件目錄，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
2020-12-12
關(guān)于JAVA經(jīng)典算法40題(超實(shí)用版)
本篇文章小編為大家介紹一下，關(guān)于JAVA經(jīng)典算法40題(超實(shí)用版)，有需要的朋友可以參考一下
2013-04-04
Java自定義實(shí)現(xiàn)equals()方法過程解析
這篇文章主要介紹了Java自定義實(shí)現(xiàn)equals()方法過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2020-02-02
SpringMVC Controller解析ajax參數(shù)過程詳解
這篇文章主要介紹了SpringMVC Controller解析ajax參數(shù)過程詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2020-07-07
Jlabel實(shí)現(xiàn)內(nèi)容自動換行簡單實(shí)例
這篇文章主要介紹了Jlabel實(shí)現(xiàn)內(nèi)容自動換行簡單實(shí)例，具有一定借鑒價(jià)值,需要的朋友可以參考下
2018-01-01
SpringMVC上傳文件并保存到本地代碼實(shí)例
這篇文章主要介紹了SpringMVC上傳文件并保存到本地代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2019-11-11
idea根據(jù)實(shí)體類生成數(shù)據(jù)庫表的流程步驟
在開發(fā)的時(shí)候,經(jīng)常會遇到數(shù)據(jù)庫表結(jié)構(gòu)設(shè)計(jì)無法滿足業(yè)務(wù)的需求,需要去改動數(shù)據(jù)庫表,我們就需要去設(shè)計(jì)數(shù)據(jù)庫的字段,然后又回來增加實(shí)體類里的字段,這樣很麻煩,所以本文給大家介紹了idea根據(jù)實(shí)體類生成數(shù)據(jù)庫表的流程步驟,需要的朋友可以參考下
2024-12-12
Spring Security中防護(hù)CSRF功能詳解
這篇文章主要介紹了Spring Security中防護(hù)CSRF功能，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2023-01-01
淺談一下Java中的堆和棧
這篇文章主要介紹了一下Java中的堆和棧,Java數(shù)據(jù)類型在執(zhí)行過程中存儲在兩種不同形式的內(nèi)存中：棧和堆，它們通常由運(yùn)行Java虛擬機(jī)(JVM)的底層平臺維護(hù),需要的朋友可以參考下
2023-04-04
SpringBoot去除內(nèi)嵌tomcat的實(shí)現(xiàn)
這篇文章主要介紹了SpringBoot去除內(nèi)嵌tomcat的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2020-09-09