??前面的話??
大家好！博主開辟了一個新的專欄——劍指offer，我要開始刷題了！這個專欄會介紹《劍指offer》書上所有的面試編程題，并且會分享一些我的刷題心得，由于博主水平有限，如有錯誤，歡迎指正，如果有更好的解題思路和演算法可以分享給博主哦！一起加油！一起努力！
📒博客主頁：未見花聞的博客主頁
🎉歡迎關注🔎點贊👍收藏??留言📝
📌本文由未見花聞原創，CSDN首發！
📆首發時間：🌴2021年9月12日🌴
??堅持和努力一定能換來詩與遠方！
💭參考書籍：📚《劍指offer第1版》，📚《劍指offer第2版》
💬參考在線編程網站：🌐牛客網🌐力扣
🙏作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！
博主的碼云gitee，平常博主寫的程式代碼都在里面，
📌導航小助手📌
- ??劍指 Offer 22. 鏈表中倒數第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.
限制：
無
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
💡解題思路
方法1： 遍歷，
最直接的方法就是遍歷鏈表，第一次遍歷鏈表求出鏈表元素個數len，得到鏈表元素個數后，倒數第k個結點即第len - k + 1個結點，如果從0開始數就是第len - k個結點，所以第二次遍歷目的是找到這個結點并回傳這個結點的地址，遍歷次數為len - k + 1，
時間復雜度： O(N)
方法2： 快慢指標，
我們都知道公交車每班車次的發出都會間隔一段時間，假設每班公交車從起點站到終點站所用時間相同，那么在這種理想情況下每相鄰兩班公交車到終點站的時間差即為每相鄰兩班發車的時間差，我們可以根據這種快慢的差異思想來思考這道題，我們需要求倒數第k個結點，我們可以讓一個快指標fast先走k步，然后再讓一個慢指標slow出發，fast走一步slow也走一步，等到fast走到終點時，slow剛好走到fast前面k步的位置，也就是倒數第k個結點，
時間復雜度： O(N)
🔑源代碼
編程語言：C語言
在線編程平臺：力扣
//方法1：
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
if(!head)
return NULL;
int size = 0;
struct ListNode* cur = NULL;
cur = head;
while (cur)
{
size++;
cur = cur->next;
}
int i = 0;
cur = head;
for (i = 0; i < size - k; i++)
{
cur = cur->next;
}
return cur;
}
//方法2：
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
if (head == NULL)
{
return NULL;
}
struct ListNode* fast = head;
struct ListNode* slow = head;
int i = 0;
for(i = 0; i < k && fast; i++)
{
fast = fast->next;
}
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
🌱總結
求單鏈表倒數第k個結點，最簡單直接的方法就是遍歷求出鏈表長度然后根據鏈表長度找到目的結點的位置，更深一步，我們可以參考公交車發車的思想，根據遍歷的結點差使用快慢指標得到倒數第k個結點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299672.html
標籤：其他
上一篇：【資料結構】鏈表經典演算法題集錦