Java關于重排鏈表詳細解析
更新時間：2022年01月25日 14:51:16 作者：Fly upward
在我們平時的代碼過程中，鏈表是我們經(jīng)常遇到的一個數(shù)據(jù)結構，面試題中鏈表占很大一部分，可見鏈表操作是非常重要的。本篇文章我們來探究一下如何進行重排鏈表
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;
}
}
}
到此這篇關于Java關于重排鏈表詳細解析的文章就介紹到這了,更多相關Java 重排鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
SpringBoot 項目的部署一般采用全量jar 包方式部署相關項目,如果我們對相關的Contrller層進行相關業(yè)務調(diào)整就需要重新編譯全量jar 包太麻煩了,所以本文給大家介紹了使用SpringBoot 的增量/瘦身部署方式,需要的朋友可以參考下2024-01-01
這篇文章主要為大家詳細介紹了struts2獲取服務器臨時目錄的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-09-09
關于SpringSecurity簡介以及和Shiro的區(qū)別
這篇文章主要介紹了關于SpringSecurity簡介以及和Shiro的區(qū)別,在Java應用安全領域，Spring Security會成為被首先推崇的解決方案，就像我們看到服務器就會聯(lián)想到Linux一樣順理成章,需要的朋友可以參考下2023-07-07
這篇文章主要介紹了詳解Java豆瓣電影爬蟲——小爬蟲成長記（附源碼） ，具有一定的參考價值，有需要的可以了解一下。2016-12-12
Java中Set集合轉(zhuǎn)為List集合常見的兩種方式
List是Java中比較常用的集合類,指一系列存儲數(shù)據(jù)的接口和類,可以解決復雜的數(shù)據(jù)存儲問題,這篇文章主要給大家介紹了關于Java中Set集合轉(zhuǎn)為List集合常見的兩種方式,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了Spring解決泛型擦除的思路，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2024-01-01
這篇文章主要介紹了SpringBoot入門之集成Druid的方法示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-07-07
java編程中字節(jié)流轉(zhuǎn)換成字符流的實現(xiàn)方法
下面小編就為大家?guī)硪黄猨ava編程中字節(jié)流轉(zhuǎn)換成字符流的實現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
在?Java?中將Object?轉(zhuǎn)換為?Int的四種方法
這篇文章主要介紹了在Java中如何將?Object?轉(zhuǎn)換為Int,本文研究了在?Java中將Object轉(zhuǎn)換為int的四種不同方法，結合示例代碼給大家介紹的非常詳細，需要的朋友可以參考下2023-05-05
Netty是一個異步的、基于事件驅(qū)動的網(wǎng)絡應用框架，用于快速開發(fā)可維護、高性能的網(wǎng)絡服務器和客戶端，如果你還不了解它的使用，就趕快繼續(xù)往下看吧2022-08-08