题解 | #链表中倒数最后k个结点#
链表中倒数最后k个结点
http://www.nowcoder.com/questionTerminal/886370fe658f41b498d40fb34ae76ff9
描述
这是一篇面对初级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)
总结
各位牛友在练习的时候要注意边界条件的判定
扩展
快慢指针是链表中一种常见的处理方法
在判断链表中是否有环中也很有用
阿Q的题解 文章被收录于专栏
阿Q秋招刷过的题
投递中国石油等公司10个岗位 >
