描述

这是一篇面对初级coder的题解。
知识点：链表 栈
难度：一星

题解

题目： 输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。如果该链表长度小于k，请返回一个长度为 0 的链表。

考察链表的基础知识

方法一：栈

利用栈后进先出的特性，可以方便的提取最后k个元素 

#include <stack>
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        stack<ListNode *> stack;//栈
        ListNode *answer=NULL;//返回值
        while(pHead)//全部入栈
        {
            stack.push(pHead);
            pHead=pHead->next;
        }
        if(k>stack.size()||stack.size()==0) //判断特殊值
            return answer;
        for(int i=0;i<k;i++)
        {
            answer=stack.top();
            stack.pop();
        }
        return answer;
    }
};


运行时间 6ms  占用内存 504KB

方法二：快慢指针


要求链表的倒数第k个节点，可以采用快慢指针的方法，快指针先移动k步，然后慢指针再从头开始，这个时候快慢两个指针同时移动，当快指针到链表的末尾的时候，返回慢指针即可。
注意边界条件，如果第一个指针还没走k步的时候链表就为空了，应返回null，同时还要校核k与链表长度等长的情形
代码如下：
c++版 
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode *fast=pHead;//快指针 初始化头结点 先走一步
        ListNode *slow=NULL;//慢指针 初始化为空 长度不够直接返回
        if(pHead==NULL)
            return slow;
        for(int i=0;inext;
            if(fast==NULL&&inext;
            slow=slow->next;
        }
        return slow;
    }
};
运行时间： 2 ms 占用内存：512K
该方法空间复杂度O(1)

总结

各位牛友在练习的时候要注意边界条件的判定

扩展

快慢指针是链表中一种常见的处理方法
在判断链表中是否有环中也很有用