[算法]链表中倒数第k个节点
题目来源:牛客网剑指offer
题目:输入一个链表,输出该链表中倒数第k个结点。
解题思路:利用两个指针,第一个指针(font)指向正向第k个节点的数据,第二个指针(tail)指向头节点的数据,当font指针指向尾部的时候,tail指针就是指向了倒数第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) {
ListNode * font = pListHead;
while ((k > 0)&&(font!=NULL)) {
font = font->next;
--k;
}
if ((font == NULL) && (k != 0))return NULL;
ListNode* tail = pListHead;
while (font != NULL)
{
font = font->next;
tail = tail->next;
}
return tail;
}
};
通过截图