1. 題目

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)。為了符合大多數(shù)人的習(xí)慣，本題從1開始計(jì)數(shù)，即鏈表的尾節(jié)點(diǎn)是倒數(shù)第1個(gè)節(jié)點(diǎn)。例如，一個(gè)鏈表有6個(gè)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開始，它們的值依次是1、2、3、4、5、6。這個(gè)鏈表的倒數(shù)第3個(gè)節(jié)點(diǎn)是值為4的節(jié)點(diǎn)。

示例： 給定一個(gè)鏈表: 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 快指針先走k步
• 隨后快慢指針一起前進(jìn)，直到快指針到達(dá)NULL
• 慢指針指向倒數(shù)第k個(gè)節(jié)點(diǎn)

class Solution { public:ListNode* getKthFromEnd(ListNode* head, int k) {ListNode *fast = head, *slow = head;while(k--)fast = fast->next;while(fast){fast = fast->next;slow = slow->next;}return slow;} };

程序員面試金典 - 面試題 02.02. 返回倒數(shù)第 k 個(gè)節(jié)點(diǎn)

class Solution { public:int kthToLast(ListNode* head, int k) {ListNode *fast = head, *slow = head;while(k--)fast = fast->next;while(fast){fast = fast->next;slow = slow->next;}return slow->val;} };

總結(jié)

以上是生活随笔為你收集整理的剑指Offer - 面试题22. 链表中倒数第k个节点（快慢指针）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。