LeetCode–鏈表中倒數第k個節點
博客說明
文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！
介紹
劍指 Offer 22. 鏈表中倒數第k個節點
題目
輸入一個鏈表，輸出該鏈表中倒數第k個節點，為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點，例如，一個鏈表有6個節點，從頭節點開始，它們的值依次是1、2、3、4、5、6，這個鏈表的倒數第3個節點是值為4的節點，
示例：
給定一個鏈表: 1->2->3->4->5, 和 k = 2.
回傳鏈表 4->5.
思路
- 初始化： 前指標 former 、后指標 latter ，雙指標都指向頭節點 head ，
- 構建雙指標距離： 前指標 former 先向前走 k 步（結束后，雙指標 former 和 latter 間相距 k 步），
- 雙指標共同移動： 回圈中，雙指標 former 和 latter 每輪都向前走一步，直至 former 走過鏈表 尾節點 時跳出（跳出后， latter 與尾節點距離為 k-1，即 latter 指向倒數第 k 個節點），
- 回傳值： 回傳 latter 即可，
代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode former = head, latter = head;
for(int i = 0; i < k; i++){
former = former.next;
}
while(former != null){
former = former.next;
latter = latter.next;
}
return latter;
}
}
感謝
Leetcode
以及勤勞的自己，個人博客，GitHub
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/8277.html
標籤：Java
上一篇：SpringbootJpa級聯保存，執行了比預料中更多的洗掉陳述句
下一篇：問一下，在idea中，如果有一段前端代碼給我，但是那個專案特別大，前端頁面都幾十百多個，我怎么快速找到那段代碼所在的檔案