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)文章
關(guān)于@JsonProperty和@JSONField注解的區(qū)別及用法
這篇文章主要介紹了關(guān)于@JsonProperty和@JSONField注解的區(qū)別及用法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
java操作json對象出現(xiàn)StackOverflow錯誤的問題及解決
這篇文章主要介紹了java操作json對象出現(xiàn)StackOverflow錯誤的問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
SpringCloud超詳細(xì)講解Feign聲明式服務(wù)調(diào)用
Feign可以把Rest的請求進(jìn)行隱藏，偽裝成類似Spring?MVC的Controller一樣。不用再自己拼接url，拼接參數(shù)等等操作，一切都交給Feign去做2022-06-06
這篇文章主要給大家介紹了關(guān)于java唯一字符串ID生成方案的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
這篇文章主要介紹了提升java開發(fā)效率工具lombok使用爭議到底該不該使用的分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
maven依賴包沖突SLF4J:?Class?path?contains?multiple?SLF4J?bi
這篇文章主要給大家介紹了關(guān)于maven依賴包沖突SLF4J:?Class?path?contains?multiple?SLF4J?bindings的處理方法,這個問題通常是因為項目中存在多個SLF4J的實現(xiàn)綁定（bindings）導(dǎo)致的沖突,需要的朋友可以參考下2024-02-02
本文主要介紹了java為什么不建議用equals判斷對象相等，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
這篇文章主要介紹了Java動態(tài)代理（設(shè)計模式）代碼詳解，具有一定借鑒價值,需要的朋友可以參考下2017-12-12
這篇文章主要介紹了mybatis in查詢條件過長的解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-10-10
springboot如何開啟一個監(jiān)聽線程執(zhí)行任務(wù)
這篇文章主要介紹了springboot如何開啟一個監(jiān)聽線程執(zhí)行任務(wù)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02