首页 > 其他 > 详细

链表中倒数第k个结点

时间:2015-05-13 21:52:17      阅读:212      评论:0      收藏:0      [点我收藏+]

题目:

输入一个单向链表,输出该链表中倒数第k个结点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾结点是倒数第1个结点。例如一个链表有6个结点,从头开始它们的值依次是1,2,3,4,5,6。这个链表的倒数第3个结点是值为4的结点。

链表结点定义如下:

struct ListNode
{
	int       m_nKey;
	ListNode* m_pNext;
};

        为了实现只遍历链表一次就能找到倒数第k个结点,我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1,第二个指针保持不动;从第k步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1,当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针止好是倒数第k个结点。

ListNode *FindKthTail(ListNode *pHead, int k)
{
	if (pHead==NULL||k==0)
		return NULL;
	//定义两个指针变量
	ListNode *pforward=NULL;
	ListNode *pbackward=NULL;
	//指针变量初始都指向头结点
	pforward=pbackward=pHead;

	for (int i=0; i<k-1; i++)
	{
		if(pbackward->m_pNext!=NULL)
			pbackward=pbackward->m_pNext;
		else//k大于链表长度
			return NULL;
	}
	while(pbackward->m_pNext!=NULL)
	{
		pbackward=pbackward->m_pNext;
		pforward=pforward->m_pNext;
	}
	return pforward;
}


链表中倒数第k个结点

原文:http://blog.csdn.net/lsh_2013/article/details/45698439

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!