本文共 982 字，大约阅读时间需要 3 分钟。

题目描述

输入一个链表，输出该链表中倒数第k个结点。

思路

想试着用一下栈，代码1是用栈的写法，代码2是用双指针的写法。

本题也考察鲁棒性，情况得考虑周全，忘了一种k可能等于0的情况。

代码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 == NULL || k == 0){
return NULL;
}
stack
   
     s;
    
ListNode* p = pListHead;
    
while(p!=NULL){
    
s.push(p);
    
p=p->next;
    
}
    
if(s.size() < k){
    
return NULL;
    
}
    
for(int i = 1;i < k;i++){
    
s.pop();
    
}
    
return s.top();
    
}};
   

代码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 == NULL || k == 0){
return NULL;
}
ListNode* p1 = pListHead;
ListNode* p2 = pListHead;
for(int i = 0;i < k;i++){
if(p2 == NULL){
return NULL;
}
else{
p2=p2->next;
}
}
while(p2!=NULL){
p1=p1->next;
p2=p2->next;
}
return p1;
}};

转载地址：https://blog.csdn.net/hanmin822/article/details/105504268 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！