Java輸出鏈表倒數(shù)第k個(gè)節(jié)點(diǎn)
問題描述
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。(尾結(jié)點(diǎn)是倒數(shù)第一個(gè))
結(jié)點(diǎn)定義如下：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
思路1：
先遍歷鏈表，計(jì)算其長(zhǎng)度length;
然后計(jì)算出倒數(shù)第k個(gè)結(jié)點(diǎn)就是正數(shù)第length - k + 1.
最后再遍歷鏈表，找到所求結(jié)點(diǎn)
時(shí)間復(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è)置兩個(gè)指針，一個(gè)初始化指向第一個(gè)結(jié)點(diǎn)，第二個(gè)指向第k個(gè)結(jié)點(diǎn)。然后兩個(gè)指針同步向后移動(dòng)，當(dāng)?shù)诙€(gè)指向尾結(jié)點(diǎn)時(shí)，第一個(gè)指針即指向了倒數(shù)第k個(gè)結(jié)點(diǎn)
代碼：
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個(gè)結(jié)點(diǎn)。
然而這改變了原本的鏈表，且并不會(huì)比思路2更高效
鏈表反轉(zhuǎn)：參考《Java語言實(shí)現(xiàn)反轉(zhuǎn)鏈表代碼示例》
總結(jié)
以上就是本文關(guān)于Java輸出鏈表倒數(shù)第k個(gè)節(jié)點(diǎn)的全部?jī)?nèi)容，感興趣的朋友可以繼續(xù)參閱：Java編程刪除鏈表中重復(fù)的節(jié)點(diǎn)問題解決思路及源碼分享、Java編程實(shí)現(xiàn)從尾到頭打印鏈表代碼實(shí)例以及本站其他相關(guān)專題，如有不足之處，歡迎留言指出，小編一定及時(shí)更正，給大家更好的閱讀體驗(yàn)和幫助，感謝朋友們對(duì)本站的支持！
相關(guān)文章
關(guān)于@JsonProperty和@JSONField注解的區(qū)別及用法
這篇文章主要介紹了關(guān)于@JsonProperty和@JSONField注解的區(qū)別及用法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-08-08
java操作json對(duì)象出現(xiàn)StackOverflow錯(cuò)誤的問題及解決
這篇文章主要介紹了java操作json對(duì)象出現(xiàn)StackOverflow錯(cuò)誤的問題及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-06-06
SpringCloud超詳細(xì)講解Feign聲明式服務(wù)調(diào)用
Feign可以把Rest的請(qǐng)求進(jìn)行隱藏，偽裝成類似Spring?MVC的Controller一樣。不用再自己拼接url，拼接參數(shù)等等操作，一切都交給Feign去做2022-06-06
這篇文章主要給大家介紹了關(guān)于java唯一字符串ID生成方案的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
提升java開發(fā)效率工具lombok使用爭(zhēng)議
這篇文章主要介紹了提升java開發(fā)效率工具lombok使用爭(zhēng)議到底該不該使用的分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
maven依賴包沖突SLF4J:?Class?path?contains?multiple?SLF4J?bi
這篇文章主要給大家介紹了關(guān)于maven依賴包沖突SLF4J:?Class?path?contains?multiple?SLF4J?bindings的處理方法,這個(gè)問題通常是因?yàn)轫?xiàng)目中存在多個(gè)SLF4J的實(shí)現(xiàn)綁定（bindings）導(dǎo)致的沖突,需要的朋友可以參考下2024-02-02
本文主要介紹了java為什么不建議用equals判斷對(duì)象相等，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
Java動(dòng)態(tài)代理（設(shè)計(jì)模式）代碼詳解
這篇文章主要介紹了Java動(dòng)態(tài)代理（設(shè)計(jì)模式）代碼詳解，具有一定借鑒價(jià)值,需要的朋友可以參考下2017-12-12
這篇文章主要介紹了mybatis in查詢條件過長(zhǎng)的解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10
springboot如何開啟一個(gè)監(jiān)聽線程執(zhí)行任務(wù)
這篇文章主要介紹了springboot如何開啟一個(gè)監(jiān)聽線程執(zhí)行任務(wù)問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02