找到链表的中间结点
- 题目描述：
输入一个链表，输出该链表中倒数第k个结点
示例：
- 解题思路：
- 一般思路：
遍历链表两次
- 高效思路：
- 使用两个指针
- 快指针先走k步
- 慢指针再与快指针一起走
- 当快指针走完时，慢指针走到倒数第k个结点
注意：k的大小可能超过链表长度这一特殊情况
注：这里我们来实现高效思路
参考代码：
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pListHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { //链表不为NULL if(pListHead==NULL) return NULL; struct ListNode* slow=pListHead,*fast=pListHead; while(k--) { //节点数量比k小 if(fast==NULL) return NULL; fast=fast->next; } //fast为NULL则停止 while(fast) { fast=fast->next; slow=slow->next; } return slow; }
- 结果：
每日k题无烦恼，点赞学习不得了~
