快慢指针法的应用

所谓快慢指针法，指的是用两个前进步长不一致的指针对链表进行遍历。

1、快慢指针定位链表中点。

该方法不借助计数器变量实现寻找链表的中间结点。

原理：

快指针的移动速度是慢指针移动速度的2倍，因此当快指针到达链表尾时，慢指针到达中点。
（当然，由于链表长度可能是奇数也可能是偶数，是否真的是中点还需要再判断）

部分代码如下。

    ListNode* fastPtr = head;
    ListNode* slowPtr = head;
    while (fastPtr && fastPtr->next)
    {
        fastPtr = fastPtr->next->next;
        slowPtr = slowPtr->next;
    }
    printf(slowPtr->val);

效率分析：

部分帖子认为快慢指针的运行效率为O(N/2)。但我在用C++实际运行测试时，发现快慢指针遍历与普通遍历在查找中点时的效率基本相同。
测试模式：将长度为1000的单链表遍历100000次。

测试代码：

#include<cstdio>
#include<Windows.h>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

int travelMode1(ListNode* head)
{
    int count = 0;
    ListNode* p = head;
    while (p)
    {
        p = p->next;
        ++count;
    }
    count = count >> 1;
    p = head;
    while (count--)
    {
        p = p->next;
    }
    return 0;
}
int TravelMode2(ListNode* head)
{
    ListNode* fastPtr = head;
    ListNode* slowPtr = head;
    while (fastPtr && fastPtr->next)
    {
        fastPtr = fastPtr->next->next;
        slowPtr = slowPtr->next;
    }
    return 0;
}

int main()
{
    ListNode* head = new ListNode(0);
    ListNode* p = head, *p1 = NULL;
    for (int i = 0; i < 1000; ++i)
    {
        p1 = new ListNode(0);
        p->next = p1;
        p = p1;
    }

/*以上代码建立了一个长度为1000的单链表*/
    DWORD start = GetTickCount64();
    for (int i = 0; i < 100000; ++i)
        travelMode1(head);
    DWORD end = GetTickCount64();
    printf("普通遍历时间： %dms\n", end - start);


    start = GetTickCount64();
    for (int i = 0; i < 100000; ++i)
        travelMode1(head);
    end = GetTickCount64();
    printf("快慢指针遍历时间： %dms\n", end - start);

    return 0;
}

运行结果：
普通遍历时间： 797ms
快慢指针遍历时间： 734ms

猜测：尽管快慢指针法循环次数仅有n/2，但是由于while循环的判定条件增多、fastPtr = fastPtr->next->next这句代码也需要消耗时间，所以快慢指针法的效率没有想象中那么高。

2、快慢指针判断链表回路 \ 查找回路入口

判断是否存在回路：

类似跑步： 两个人以恒定速度绕圈跑，假如速度不一致，那么这两个人一定会在某时刻相遇。

定义一个步长为2的快指针、一个步长为1的慢指针

当快指针到达NULL，则无环。
当快慢指针相遇，则有环。

思考：单纯的遍历链表能不能判断是否有环呢？
答案是不能。
找到NULL就是无环。
但是假如有环，无法判定函数的结束。

bool exitLoop(ListNode* head)
{
    ListNode* fastPtr = head;
    ListNode* slowPtr = head;
    while (fastPtr && fastPtr->next)
    {
        fastPtr = fastPtr->next->next;
        slowPtr = slowPtr->next;
        if (fasePtr == slowPtr)
            return true;
    }
    return false;
}

若已经判断出回路，可以进一步做以下功能：

• 测量环的长度
• 寻找环的入口

测量环的长度：只需要在环中找到两个指针，一个保持不动、一个进行遍历。两个指针相遇时遍历次数即为环的长度。

寻找环的入口：先测得环的长度为L，定义两个指针，均指向头节点。其中一个指针先前进L个结点。然后两个指针均以步长1进行遍历。
当两个指针相遇时，所指地址即为入口。