1 快慢指针

概念：所谓快慢指针中的快慢指的是指针向前移动的步长，每次移动的步长较大即为快，步长较小即为慢，常用的快慢指针一般是在单链表中让快指针每次向前移动2，慢指针则每次向前移动1。

应用：提高查找性能性能

2 如何快速找出未知长度单链表的中间节点？

普通方法：先遍历一遍单链表确定其长度L后，再从头节点出发循环L/2次即可查找到单链表的中间节点。该问题如果采用普通的方法虽然简单，但是查找效率太低。

快慢指针：设置两个指针*fast、*slow都指向单链表的头节点，其中*fast的移动速度是*slow的2倍，当*fast指向末尾节点的时候，slow正好就在中间了，可以大大提高查找的效率。

当然，此时算法还要考虑链表结点个数的奇偶数因素，当快指针移动x次后到达表尾（1+2x），说明链表有奇数个结点，直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点，说明链表结点个数是偶数，这时可以实际情况返回上中位数或下中位数或（上中位数+下中位数）/2。

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;
　　}
}

3 如何快速检测单链表是否存在循环？

利用快慢指针的原理，同样设置两个指针*fast、*slow都指向单链表的头节点，其中*fast的移动速度是*slow的2倍。如果*fast=NULL，说明该单链表以NULL结尾，不是循环链表；如果*fast=*slow，则快指针追上慢指针，说明该链表是循环链表。

fast=slow=head;
fast=fast->next->next;
while（true）{
    if (fast==NULL || fast->next==NULL)//不存在循环
        return false;
    else if (fast==slow || fast->next==slow)//存在循环
        return true;
    else{
        fast=fast->next->next;
        slow=slow->next;
}

以上内容来自于：

• twobin_快慢指针

最后

以上就是幽默星月最近收集整理的关于快慢指针【转载】1 快慢指针2 如何快速找出未知长度单链表的中间节点？3 如何快速检测单链表是否存在循环？的全部内容，更多相关快慢指针【转载】1内容请搜索靠谱客的其他文章。