溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
利用Java怎么將鏈表輸出到倒數第k個節點？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
問題描述
輸入一個鏈表，輸出該鏈表中倒數第k個結點。
結點定義如下：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}思路1：
先遍歷鏈表，計算其長度length;
然后計算出倒數第k個結點就是正數第length - k + 1.
最后再遍歷鏈表，找到所求結點
時間復雜度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：
期待只遍歷鏈表一次就能得到。
設置兩個指針，一個初始化指向第一個結點，第二個指向第k個結點。然后兩個指針同步向后移動，當第二個指向尾結點時，第一個指針即指向了倒數第k個結點
代碼：
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：
將鏈表反轉，那么原問題就變為求正數第k個結點。
然而這改變了原本的鏈表，且并不會比思路2更高效
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
