链表系列之快慢指针

快慢指针核心

快慢指针是链表问题中最经典的算法技巧之一

核心思想是使用两个指针同时遍历链表，但移动速度不同：

• 快指针每次移动2步
• 慢指针每次移动1步

这个简单的速度差异，能够解决环检测、找中点、定位特定位置等一系列问题

---

应用场景一：检测链表是否有环

LeetCode 141. 环形链表

问题描述

给定一个链表，判断链表中是否有环

核心思路

如果链表有环，快慢指针最终一定会相遇

就像在操场跑步，速度快的人一定会追上速度慢的人

代码实现

bool hasCycle(struct ListNode *head) {
    if (head == NULL) {
         return false;
    }

    struct ListNode* slow = head;
    struct ListNode* fast = head->next;

    while(slow != fast) {
        if (fast == NULL || fast->next == NULL) {
            return false;
        }

        slow = slow->next;
        fast = fast->next->next;
    }

    return true;
}

关键点

• 快指针走两步前要判断 fast->next 是否为空
• 快慢指针初始位置可以不同（一个在head，一个在head->next）
• 循环条件是 slow != fast

---

应用场景二：找到环的入口节点

LeetCode 142. 环形链表 II

问题描述

如果链表有环，找到环的起始节点

核心思路（Floyd判圈算法）

这是快慢指针最精妙的应用，分为两个阶段：

第一阶段：判断是否有环

• 快慢指针同时从head出发
• 快指针每次2步，慢指针每次1步
• 如果相遇，说明有环

第二阶段：寻找环起点

• 将一个指针放回链表头
• 两个指针都改为每次走1步
• 再次相遇的点就是环起点

数学证明

设链表头到环入口距离为 a，环入口到相遇点距离为 b，相遇点到环入口距离为 c

相遇时：

• 慢指针走了：a + b
• 快指针走了：a + b + c + b = a + 2b + c

因为快指针速度是慢指针2倍，所以：

• 2(a + b) = a + 2b + c
• 化简得：a = c

这就是为什么从头节点和相遇点同时出发，会在环入口相遇

代码实现

struct ListNode *detectCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return NULL;
    }
    
    // 关键：slow和fast都从head开始
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    // 第一阶段：判断是否有环
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            // 第二阶段：寻找环起点
            fast = head;
            while (fast != slow) {
                fast = fast->next;
                slow = slow->next;
            }
            return slow;  // 环起点
        }
    }
    
    return NULL;  // 无环
}

关键点

• 第一阶段slow和fast必须从同一位置出发
• 相遇后将其中一个指针移回head
• 第二阶段两个指针都是每次走1步

---

应用场景三：删除倒数第N个节点

LeetCode 19. 删除链表的倒数第 N 个结点

问题描述

给定一个链表，删除倒数第N个节点

核心思路

让快指针先走N步，然后快慢指针同时前进

当快指针到达末尾时，慢指针正好在倒数第N个节点的前一个位置

代码实现

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    if(head->next==NULL)
        return NULL;
    
    struct ListNode dummy;
    struct ListNode* curr = &dummy;
    dummy.next = head;
    
    struct ListNode* fast=curr;
    struct ListNode* low=curr;
    
    // 快指针先走n步
    for(int i=0;i<n;i++){
        fast=fast->next;
    }
    
    // 快慢指针同时前进
    while(fast->next!=NULL){
        low=low->next;
        fast=fast->next;
    }
    
    // 删除节点
    struct ListNode* tmp=low->next;
    low->next=low->next->next;
    free(tmp);
    
    return dummy.next;
}

关键点

• 使用虚拟头节点，避免处理删除头节点的边界情况
• 快指针要先走N步
• 慢指针停在待删除节点的前一个位置

---

应用场景四：判断回文链表

LeetCode 234. 回文链表

问题描述

判断一个链表是否为回文结构

核心思路

1. 用快慢指针找到链表中点
2. 反转后半部分链表
3. 比较前后两部分是否相同

代码实现

// 反转链表辅助函数
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
        return NULL;
    
    struct ListNode* cur=head;
    struct ListNode* prev=NULL;
    struct ListNode* next;
    
    while(cur){
        next=cur->next;
        cur->next=prev;
        prev=cur;
        cur=next;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head) {
    if(head->next==NULL){
        return true;
    }

    struct ListNode* low=head;
    struct ListNode* fast=head;
    struct ListNode* tmp;
    struct ListNode* head_behind;
    struct ListNode* head_ahead;
    
    // 快慢指针找中点
    while(fast && fast->next){
        low=low->next;
        fast=fast->next->next;
    }

    // 根据链表奇偶判断后半段起点
    if(fast){
        tmp=low->next;  // 奇数个节点
    }
    else{
        tmp=low;  // 偶数个节点
    }
    
    // 反转后半部分
    head_behind=reverseList(tmp);
    head_ahead=head;

    // 比较两部分
    while(head_behind){
        if(head_behind->val==head_ahead->val){
            head_ahead=head_ahead->next;
            head_behind=head_behind->next;
        }
        else{
            return false;
        }
    }
    return true;
}

关键点

• 快指针走到末尾时，慢指针在中点
• 要区分链表节点个数的奇偶性
• 空间复杂度O(1)，优于使用栈的方案

---

应用场景五：链表排序中找中点

LeetCode 148. 排序链表

问题描述

对链表进行排序，要求时间复杂度O(n log n)

核心思路

使用归并排序：

1. 用快慢指针找中点，分割链表
2. 递归排序左右两部分
3. 合并两个有序链表

代码实现

// 找到链表中间节点
struct ListNode* findMiddle(struct ListNode* head) {
    if (!head || !head->next) return head;
    
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;  // fast从head->next开始
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

// 合并两个有序链表
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;
    
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

// 递归归并排序主函数
struct ListNode* sortList(struct ListNode* head) {
    // 递归终止条件
    if (!head || !head->next) {
        return head;
    }
    
    // 1. 找到中间节点并分割
    struct ListNode* mid = findMiddle(head);
    struct ListNode* right = mid->next;
    mid->next = NULL;  // 切断链表
    
    // 2. 递归排序左右两部分
    struct ListNode* leftSorted = sortList(head);
    struct ListNode* rightSorted = sortList(right);
    
    // 3. 合并有序链表
    return merge(leftSorted, rightSorted);
}

关键点

• 快指针从head->next开始，确保分割点在左半部分
• 分割后要将左半部分的尾节点指向NULL
• 归并排序是链表排序的最优解

---

快慢指针核心总结

基本模板

struct ListNode* slow = head;
struct ListNode* fast = head;

while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}

注意事项

1. 空指针判断：快指针移动前要判断fast和fast->next
2. 初始位置：根据具体问题选择是否从同一位置开始
3. 奇偶处理：找中点时要注意链表长度奇偶的影响

---

总结

快慢指针是链表算法中最优雅的技巧之一

它用简单的速度差异，解决了环检测、找中点、定位等多个经典问题