Java輸出鏈表倒數(shù)第k個節(jié)點
問題描述
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。(尾結(jié)點是倒數(shù)第一個)
結(jié)點定義如下：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
思路1：
先遍歷鏈表，計算其長度length;
然后計算出倒數(shù)第k個結(jié)點就是正數(shù)第length - k + 1.
最后再遍歷鏈表，找到所求結(jié)點
時間復(fù)雜度O(2n),需要遍歷兩次鏈表
代碼如下：
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0){
return null;
}
//直接遍歷
ListNode p = head;
int length = 1;
while(p.next != null){
length++;
p = p.next;
}
int index = length - k + 1;
if(index <= 0){
return null;
}
p = head;
int num = 1;
while(p.next != null && num < index){
num++;
p = p.next;
}
if(num < index){
return null;
}else{
return p;
}
}
思路2：
期待只遍歷鏈表一次就能得到。
設(shè)置兩個指針，一個初始化指向第一個結(jié)點，第二個指向第k個結(jié)點。然后兩個指針同步向后移動，當(dāng)?shù)诙€指向尾結(jié)點時，第一個指針即指向了倒數(shù)第k個結(jié)點
代碼：
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0){
return null;
}
//直接遍歷
ListNode p = head;
ListNode q = head;
for(int i = 0; i < k-1; i++){
if(q == null){
return null;
}
q = q.next;
}
if(q == null){
return null;
}
while(q.next != null){
p = p.next;
q = q.next;
}
return p;
}
思路3：
將鏈表反轉(zhuǎn)，那么原問題就變?yōu)榍笳龜?shù)第k個結(jié)點。
然而這改變了原本的鏈表，且并不會比思路2更高效
鏈表反轉(zhuǎn)：參考《Java語言實現(xiàn)反轉(zhuǎn)鏈表代碼示例》
總結(jié)
以上就是本文關(guān)于Java輸出鏈表倒數(shù)第k個節(jié)點的全部內(nèi)容，感興趣的朋友可以繼續(xù)參閱：Java編程刪除鏈表中重復(fù)的節(jié)點問題解決思路及源碼分享、Java編程實現(xiàn)從尾到頭打印鏈表代碼實例以及本站其他相關(guān)專題，如有不足之處，歡迎留言指出，小編一定及時更正，給大家更好的閱讀體驗和幫助，感謝朋友們對本站的支持！
相關(guān)文章
本文給大家分享編寫一個簡單的mybatis進(jìn)行插入數(shù)據(jù)的實例代碼，非常不錯具有參考借鑒價值，感興趣的朋友一起看看吧2016-10-10
5分鐘快速搭建SpringBoot3?+?MyBatis-Plus工程/項目的實現(xiàn)示例
本文主要介紹了使用IntelliJ?IDEA創(chuàng)建Spring?Boot工程,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2025-01-01
這篇文章主要為大家詳細(xì)介紹了Java如何將大文件切割成小文件，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
Java利用Hutool-Script封裝JS腳本執(zhí)行
在?Java?開發(fā)中,有時需要動態(tài)執(zhí)行腳本代碼,比如?JavaScript?腳本,來實現(xiàn)一些靈活的業(yè)務(wù)邏輯,下面我們就來看看如何利用Hutool-Script模塊對Java的腳本執(zhí)行功能進(jìn)行封裝吧2025-02-02
這篇文章主要介紹了jpanel設(shè)置背景圖片的二個小例子，實現(xiàn)了動態(tài)加載圖片做背景的方法,需要的朋友可以參考下2014-03-03
Spring Boot2配置Swagger2生成API接口文檔詳情
這篇文章主要介紹了Spring Boot2配置Swagger2生成API接口文檔詳情，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-09-09
這篇文章主要介紹了從零開始SSM搭建步驟(圖文)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
關(guān)于SpringMVC請求域?qū)ο蟮臄?shù)據(jù)共享問題
這篇文章主要介紹了SpringMVC請求域?qū)ο蟮臄?shù)據(jù)共享問題，本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-02-02
本篇是Hadoop源碼分析系列文章第三篇，主要介紹Hadoop啟動以及腳本的剖析，后續(xù)本系列文章會持續(xù)更新，有需要的朋友可以借鑒參考下2021-09-09
正則表達(dá)式，又稱規(guī)則表達(dá)式,是一種文本模式。正則表達(dá)式使用單個字符串來描述、匹配一系列匹配某個句法規(guī)則的字符串，通常被用來檢索、替換那些符合某個模式（規(guī)則）的文本。本文將通過示例為大家詳細(xì)說說Java正則表達(dá)式的使用，感興趣的可以了解一下2022-08-08