快慢指针：妙解查找链表的中间结点问题

快慢指针：妙解查找链表的中间结点问题

引用

CSDN

1.

https://blog.csdn.net/2302_80190394/article/details/136767602

链表是一种常见的数据结构，其中每个元素（节点）包含数据和指向下一个节点的指针。在某些算法和数据处理场景中，找到链表的中间节点是一个常见的需求，例如在合并排序算法中。本文将介绍如何使用快慢指针算法高效地找到链表的中间节点。

给你单链表的头结点 head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例 1：

**输入：**head = [1,2,3,4,5]
**输出：**[3,4,5]
**解释：**链表只有一个中间结点，值为 3 。

示例 2：

**输入：**head = [1,2,3,4,5,6]
**输出：**[4,5,6]
**解释：**该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

方法一：暴力求解

思路：遍历所有节点，找到中间节点，再次遍历，返回中间节点指针

//若需要遍历完所有节点，则是while（start）而不是start->next
struct ListNode* middleNode(struct ListNode* head) {
    
    struct ListNode* start = head;
    int count = 0;
    while(start){   //若只有一个元素，则只是循环一轮
        count++;
        start = start->next;        //控制语句
    }
    int count2 = 0;
    start = head;
    while(count2 < (count / 2))
    {
        start = start->next;
        count2++;
    }
    return start;
}  

缺点：需要两次遍历，时间长。

方法二：快慢指针法

思路：建立fast和slow指针，当fast指针走两步时，slow指针才走一步。

struct ListNode* middleNode(struct ListNode* head) {
    
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast){
        if(fast->next){
        fast = fast->next->next;
        slow = slow->next;
        }
        else
            fast = fast->next;
    }
    return slow;
}  

需要注意的是：在else语句中，slow不能前进！只有fast连续走两步时，slow才可以往下进行！此时，大大增加了时间效率。

优化代码：

while(fast  && fast->next ){
    // if(fast->next){
    fast = fast->next->next;
    slow = slow->next;
    // }
    // else
        // fast = fast->next;
}
return slow;

需要注意的是，不能用 || ，或： 若其中一个为真，则进入循环，当fast->next为假时，fast可以为真！