链表——求链表中倒数第k个节点
链表中倒数第k个结点
http://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a
思路：
①我第一次做这题，选择是将整个链表反转，再输出第k个，但是有个问题就“第k个节点”的意思是从第k个到最后的所有链表。
例：1->2->3->4的第二个节点是2->3->4。
所以反转链表不行，但是如果是求第k个节点的值，就没有问题了。
②采用快慢指针
这种方法以前在做求链表中间节点时遇到过。
设定两个指针，一个比另一个快k个，这样，当fast到达尾（null）时，另一个就处于倒数k个。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(!pListHead||k<=0) return nullptr;
ListNode* fast = pListHead;
ListNode* slow = pListHead;
while(k--)
{
if(fast)
{
fast=fast->next;
}
else
{
return nullptr;
}
}
while(fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
};```
字节跳动二面573人在聊
查看2道真题和解析