题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路
- 倒数第K个节点？？？
- 先求总长度 len
- p遍历到 len-k个节点
- q从头开始遍历，p也同时遍历，到达尾部时。q指向的就是倒数第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* p = pListHead;
ListNode* q = pListHead;
int count = 0;
// 非法判断
if (k <= 0) return nullptr;
// 统计链表节点数量
while(count < k && p != nullptr){
p = p->next;
count++;
}
if (p == nullptr ){// 提前结束了节点
if (count < k){// size < k,节点数量小于k
return nullptr;
}else {// size = k，节点数量恰好等于k
return q;
}
}
// size > k，节点数量大于k，两个指针同时移动，直到到达倒数第k个节点
while(p != nullptr){
q = q->next;
p = p->next;
}
return q;
}
};
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
