文章目錄
- 題目內容：
- 思路一：鏈表長度法
- 思路二：雙指標先行法
題目內容：
輸入一個鏈表，輸出該鏈表中倒數第k個節點，為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點，
例如，一個鏈表有 6 個節點，從頭節點開始，它們的值依次是 1、2、3、4、5、6，這個鏈表的倒數第 3 個節點是值為 4 的節點，
leetcode題目鏈接（點擊即可跳轉）：鏈表中倒數第k個節點
題目理解：這個題目要求我們找到倒數第k個節點，順數的最后一個元素是倒數第1個節點（有的地方會把這里叫做倒數第0個，但是這個題目已經說的很清楚了，是倒數第一個）
假設我們的鏈表是這樣的，如果要求倒數第2個節點，那么我們應該是找到值為5的這個節點，（下面的講解默認以該圖為例）
題目中給的是單鏈表，也就是我們無法從“6”直接找到“5”，而且單鏈表的頭指標head也有可能指向NULL（也就是鏈表一個元素都沒有）
思路一：鏈表長度法
核心思路：既然我們沒法從后往前走，只能從鏈表的頭走到尾，那么我們可以先遍歷鏈表求出長度length，然后將倒數第k個節點轉換成求順數第n個節點，n = length - k + 1，（比如說倒數第1個節點實際上就是順數的第6個節點，倒數第2個節點就是順數第5個節點），然后再從頭遍歷鏈表，找到順數第n個節點回傳即可，
注意：
1）鏈表為空時需要單獨處理！（直接回傳head或者NULL均可，推薦NULL，方便閱讀）
2）題目中k的取值范圍并沒有說明，所以我們應該考慮為k任意取值，當k取負數，或者k的大小大于length的時候，此時應該超出鏈表范圍了，應該單獨處理！（直接回傳NULL）
代碼實作：
//方法一：鏈表長度法
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
//判斷是否為空鏈表
if(head == NULL)
return NULL;
//遍歷求出鏈表長度
int length = 0;
struct ListNode* cur = head;
while(cur)
{
cur = cur->next;
length++;
}
//對k的取值范圍做一個限定
if(k < 0 || k > length)
return NULL;
int n = length - k + 1;//k的大小未定，取值范圍未定，有坑！
cur = head;
while(n-- != 1)
{
cur = cur->next;
}
return cur;
}
上面這種方法雖然實作了求第k個節點，但是因為遍歷了兩遍鏈表，實際上效率有所損失，有沒有更好的方法呢？先看一下下面的圖找一找規律吧！
不難看出應該存在關系 順數第n個和倒數第k個加起來的和是一個定值，為鏈表的長度+1
也就是n + k = length + 1；理解這個后，我們接下來介紹第二種方法
思路二：雙指標先行法
核心思想：我們創建兩個指標都指向頭節點，讓一個先走k步，然后兩個指標一起走，當先走的指標到達尾節點指向的NULL時，就停止！
注意：
1）鏈表為空時需要單獨處理！（直接回傳head或者NULL均可，推薦NULL，方便閱讀）
2）題目中k的取值范圍并沒有說明，所以我們應該考慮為k任意取值，當k取負數，或者k的大小大于length的時候，此時應該超出鏈表范圍了，應該單獨處理！（這個時候先走的指標會提前指向NULL，這個時候就需要停止并回傳NULL）
代碼實作：
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
if(head == NULL)
return NULL;
struct ListNode* fast = head;//快指標先走
struct ListNode* slow = head;//慢指標后走
while(k--)//k不為0，fast就繼續往后走
{
if(fast == NULL)//需要判斷fast是否已經走到NULL了
return NULL;
fast = fast->next;
}
//快慢指標手拉手，一起走
while(fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/292721.html
標籤：其他