学会了让节点手拉手，接下来该带它们出去玩了。链表的经典题目里，藏着一个反复出现的小游戏——快慢指针的追追跑跑。两只指针一起出发，一只快一点，一只慢一点，好多谜题就在这场追逐里悄悄解开。

快慢指针：找一个中间的它

想找链表的中间节点（力扣 876 链表的中间结点），不用先数长度。慢指针一次走一步，快指针一次走两步，等快指针跑到尽头，慢指针恰好站在正中间：

struct ListNode* midNode(struct ListNode* head)
{
    struct ListNode* slow, * fast;
    slow = fast = head;              // 一起从起点出发
    while (fast && fast->next)
    {
        slow = slow->next;           // 慢慢走
        fast = fast->next->next;     // 快快跑
    }
    return slow;
}

循环条件 fast && fast->next 一个都不能少：节点数为奇数时 fast 会刚好停在末尾，为偶数时 fast 会落到 NULL，两种都要接住。

翻转链表：把队伍掉个头

把整条链表反过来（力扣 206 反转链表），用「逐个头插」的思路最直观：从头挨个摘下节点，插到新链表的最前面。

struct ListNode* reverse(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* newnode = NULL;
    while (cur)
    {
        struct ListNode* next = cur->next;  // 先记住下一只手
        cur->next = newnode;                // 掉头，牵向新链表
        newnode = cur;                      // 新链表头更新
        cur = next;
    }
    return newnode;
}

回文链表：正读反读都一样

有了前两位帮忙，回文判断（牛客 链表的回文结构，力扣也有 234 回文链表）变得很优雅：先让快慢指针找到中点，把后半段翻转，然后两只指针并排往前走，逐个比较——全部相等就是回文。

bool chkPalindrome(struct ListNode* A)
{
    struct ListNode* mid = midNode(A);     // 找中点
    struct ListNode* rmid = reverse(mid);  // 翻转后半段
    while (rmid && A)
    {
        if (rmid->val != A->val)
            return false;
        A = A->next;
        rmid = rmid->next;
    }
    return true;
}

相交链表：先让长的走差距步

相交链表（力扣 160 相交链表）：两条链表可能在某处汇合、共享尾巴。先各自数出长度，如果尾节点都不是同一个，那就根本不相交；否则让长的链表先走 |len1 - len2| 步，把差距补齐，再一起往前，相遇处就是交点。

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* p1 = headA, * p2 = headB;
    int len1 = 0, len2 = 0;
    while (p1->next) { len1++; p1 = p1->next; }
    while (p2->next) { len2++; p2 = p2->next; }
    if (p1 != p2)          // 尾结点不同，注定错过
        return NULL;

    int gap = abs(len1 - len2);
    struct ListNode* longList = headA, * shortList = headB;
    if (len2 > len1)
    {
        longList = headB;  // 假设法：别猜，直接交换
        shortList = headA;
    }
    while (gap--)
        longList = longList->next;   // 长的先走差距步
    while (longList != shortList)    // 再一起走
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return shortList;
}

环形链表：操场上的追逐

判断链表有没有环（力扣 141 环形链表），还是快慢指针：在操场（环）上，快的人总会套圈追上慢的人。

bool hasCycle(struct ListNode* head)
{
    struct ListNode* slow, * fast;
    slow = fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)   // 追上了，一定有环
            return true;
    }
    return false;           // fast 先到终点，是直路
}

更妙的是找到环的入口（力扣 142 环形链表 II）：相遇之后，把相遇点处的 next 断开，环就变成了两条相交链表——是不是有点眼熟？交给上面那个「差距步」函数就好啦。

struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* slow = head, * fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)               // 相遇了
        {
            struct ListNode* tmp = slow->next;
            slow->next = NULL;          // 轻轻断开环
            return getIntersectionNode(head, tmp);
        }
    }
    return NULL;
}

愿当下的花如你所见般美丽