题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路
- 使用栈，从头到尾遍历链表，依次放到栈中，最后再一个一个从栈中拿出来，直到拿出第k个，也就是想要的结果。
- 使用快慢指针，快指针从头结点走k步后，慢指针从头结点开始一起和快指针向尾部移动，直到快指针到达尾部。
实现1-使用栈
/*
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;
stack<ListNode*> s;
ListNode* p = pListHead;
while(p)
{
s.push(p);
p = p->next;
}
ListNode* res;
while(k--)
{
if(s.empty())
return nullptr;
else
{
res = s.top();
s.pop();
}
}
return res;
}
};
实现2-快慢指针
/*
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)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
注意事项
- 当输入为
nullptr或者当k的值小于等于0时。 - 当k的值大于链表长度。
