劍指 Offer 22. 鏈表中倒數第k個節點
輸入一個鏈表，輸出該鏈表中倒數第k個節點，為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點，
例如，一個鏈表有 6 個節點，從頭節點開始，它們的值依次是 1、2、3、4、5、6，這個鏈表的倒數第 3 個節點是值為 4 的節點，
示例：
給定一個鏈表: 1->2->3->4->5, 和 k = 2.
回傳鏈表 4->5.
做題思路：
這倒題，如果熟悉鏈表的話，不論是先遍歷鏈表然后在鏈表數減去K數求得鏈表中倒數第K個節點，還是創建兩個指標，讓一個指標在k范圍內運動，再讓兩個指標同時運行，等前一個指標為慷訓者到達鏈表尾部的時候，后一個指標停下來的位置就剛好是鏈表中倒數第k個節點，
代碼1
class Solution1 {
public ListNode getKthFromEnd(ListNode head, int k) {
//創建兩個指標,在指向head
ListNode former = head, latter = head;
//一個指標在k范圍內遍歷，到k的位置停下來
for (int i = 0; i < k; i++) {
former = former.next;
}
//停下來的former指標，開始和latter同步運動，等到former == null的時候，latter也停止了下來
while (former!=null) {
former = former.next;
latter = latter.next;
}
//等latter停下來以后，剛好就在倒數第K個節點,回傳latter即可
return latter;
}
}
代碼2
class Solution2 {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode former = head, latter = head;
//設定len，然后先遍歷完former
int len = 0;
while (former != null) {
former = former.next;
len++;
}
//len - k 剛好就是倒數第K個節點
for (int i = 1; i <= len - k; i++) {
latter = latter.next;
}
return latter;
}
}
代碼3
class Solution3 {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode former = head, latter = head;
while (former != null) {
former = former.next;
//這個思路是借鑒了LeetCode上面某位大神寫的，如果k>0,k--,等k<0的時候，節點也剛好到了倒數第K個節點的位置了
if (k > 0)
k--;
else
latter = latter.next;
}
return latter;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296190.html
標籤：其他