面试15：链表中倒数第K个结点

画喜

于 2016-09-04 22:58:27 发布

阅读量257

点赞数

分类专栏：剑指offer

本文链接：https://blog.csdn.net/qq_23930393/article/details/52435404

版权

剑指offer 专栏收录该内容

15 篇文章

订阅专栏

本文介绍了一种高效算法，用于找到单链表中倒数第K个节点的方法。通过使用双指针技术，文章详细解释了如何设置两个指针之间的距离为K-1，然后同步移动指针直至后指针达到链表尾部，此时前指针正好指向目标节点。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

思路：两个指针一前一后，相差k-1，当后指针到达最后一个结点时，前一指针正好指向是所求结点

ListNode *FindKthToTail(ListNode* pListHead,unsigned int k)
{
	if(pListHead==NULL||k==0)
		return NULL;
	ListNode *pAhead=pListHead;
	ListNode *pBehind=NULL;
	
	for(unsigned int i=0;i<k-1;++i)
	{
		if(pAhead->next!=NULL)
			pAhead=pAhead->next;
		else
		{
			return NULL;
		}
	pBehind=pListHead;
	while(pAhead->next!=NULL)
	{
		pAhead=pAhead->next;
		pBehind=pBehind->next;
	}
	return pBehind;
}