如何求中间位置的数——快慢指针

Posted on | In

一个数组是有序数组，则mid=(start+end)/2即是中间位置。
倘若是一个有序链表呢？
转换为数组？——数组size怎么确定。暂时设大点吧
第一次遍历记录size，第二次再到size/2位置

也许方法很多，但是今天可以通过快慢指针来完成：

概念

快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

寻找中间位置的数

该方法在不借助计数器变量实现寻找中位数的功能。原理是：快指针的移动速度是慢指针移动速度的2倍，因此当快指针到达链表尾时，慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素，当快指针移动x次后到达表尾（1+2x），说明链表有奇数个结点，直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点，说明链表结点个数是偶数，这时可以根据“规则”返回上中位数或下中位数或（上中位数+下中位数）的一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
while (fast&&slow)
{
　　if (fast->next==NULL)
　　    return slow ->data;
　　else if (fast->next!= NULL && fast->next->next== NULL)
　　    return (slow ->data + slow ->next->data)/2;
　　else
　　{
　　    fast= fast->next;
　    　fast= fast->next;
　　    slow = slow ->next;
　　}
　}

具体地，可以拿leetcode 109题 练手。

其他用途

  • 判断单链表是否为循环链表
  • 如果链表为存在环，如果找到环的入口点？

具体可以参考下关于快慢指针的若干应用详解.