剑指offer(15)----求链表中的倒数第k个结点（扩展求链表的中间结点）

1.求链表中的倒数第K个结点

思路一：假设整个链表有n个结点，那么倒数第K个结点就是从头结点开始的第n-k+1个结点。如果我们能够得到链表中的结点个数为n,那只要从头结点开始往后走n-k+1步就可 以了。如何得到结点数n?这个不难，从头开始遍历链表每经过一个结点，结点个数增1即可。也就是说我们需要遍历链表两次，第一次统计出链表中结点的个数，第 二次就能找到链表的第k个结点，效率低些，但是面试可能要求只能遍历一次链表来完成题目

思路二：为了实现只遍历链表1次就能找到倒数第k个结点，我们可以定义两个指针pahead和pbehind，开始时，两指针都指向链表第一个结点。第一个指针pahead从链表的 头指针开始遍历向前走k-1，指向第K个结点，第二个指针pbehind保持不动；从k步开始，pbehind指针也开始从链表的头部开始遍历，同时，pahead从第k个结点， 由于两 个指针始终保持k-1个距离，因此当pahead指向链表最后一个结点时，pbehind指向链表的倒数第k个结点。

代码：

//求链表中的倒数第K个结点
Node * FindKth2Tail(node **phead,int k)
{
	if(*phead==NULL || k==0)//边界条件测试1:
	  return NULL;
	Node *pAhead=*phead;
	Node *pBehind=*phead;
	for(int i=0;i<k-1;i++)//
	{
		if(pAhead->next != NULL)//边界条件测试2：链表中结点数是否小于k
			pAhead=pAhead->next;
		else 
			return NULL;//若小于直接退出
	}
	while(pAhead->next!=NULL)
	{
		pAhead=pAhead->next;
		pBehind=pBehind->next;
	}
	return pBehind;
}

2.扩展：求链表的中间结点，如果链表的结点总数为奇数，返回中间结点，若为偶数，返回中间两个结点的任何一个。

思路：为了解决这一问题，同样可以设置两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针指向链表的尾端时，走得慢的 指针正好指向链表的中间结点

代码：

//求链表中的中间结点：当结点总数为奇数时，中间结点即为中间的结点；当结点总数为偶数时，中间结点为中间的两个结点的任意一个,
//是不是还得在这里用随机数算法从这两个结点中取随机数
Node *FindMidNode(node ** phead)
{
	if(*phead==NULL )//边界条件测试1:
	  return NULL;
	Node *pAfast=*phead;
	Node *pAslow=*phead;
	//while(pAfast->next!=NULL)//此时当结点总数为偶数时，返回的中间两个结点中的右边的那一个结点；
	//{
	//	pAslow=pAslow->next;
	//	pAfast=pAfast->next->next;
	//	if(pAfast==NULL)
	//		break;
	//}
	//return pAslow;
	while(pAfast->next!=NULL &&pAfast->next->next!=NULL)
	{
		pAslow=pAslow->next;
		pAfast=pAfast->next->next;
	}
	return pAslow;//此时当结点总数为偶数时，返回的中间两个结点中的左边的那一个结点；
}

当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让一个指针遍历的速度快一些（比如在一次走两步）；或者让它现在链表上走若干步，然后再让另一个指针开始走