寻找链表的中间节点

一、思想概述

        对于找链表的中间节点，我们往往最先想到的就是先行遍历整个链表，然后将其全部节点的个数记录下来，再从头节点开始遍历整个链表长度的1/2个节点。

        虽然这种方法可行，但效率却不高，如果碰上链表比较长的情况下，就显得有些捉襟见肘了，那么除此之外我们还能用“前后指针法”找到中间节点。

        对于整个链表长度来说，中间节点一定是整个链表长度的1/2，也就是整个链表的长度是中间节点长度的2倍，所以我们可以设置两个指针，分别为slow、fast，我们首先让慢指针slow和快指针fast都在头节点位置处，之后再让slow指针一次走一步，而fast节点一次走2步，如此一来，fast指针走的距离永远是slow指针的2倍，直到fast或fast->next为空后结束循环。

二、逻辑演示图

        对于链表的节点个数来说，共有奇数和偶数之分，对于奇数来说自然别无异议，只有一个中间节点，那么对于偶数来说，中间两个节点均可，都是中间节点。

接下来为大家绘制slow指针和fast指针走的全部流程图：

        最后，fast满足fast或fast->next为空 ，则结束循环，最后返回slow指针。

三、代码实现

//找中间节点
int FindMidNode(link* pf)
{
	assert(pf);
	link* slow = pf;
	link* fast = pf;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow->data;
}


int main()
{
	link pf;
	link* pt = &pf;
	link** ph = &pt;
	Init(ph);//初始化头节点数据域为5
	PushTail(ph, 3);//尾插
	PushTail(ph, 6);//尾插
	PushTail(ph, 1);//尾插
	PushTail(ph, 4);//尾插
	PushTail(ph, 5);//尾插
	int mid = FindMidNode(pt);//找中间节点
	printf("%d\n", mid);
	Print(ph);
	return 0;

}