链表的中间节点(C语言 -＞ 快慢指针)

题目介绍

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

// Definition for singly-linked list.
 struct ListNode 
 {
     int val;
     struct ListNode *next;
 };

题目链接：
leetcode
牛客网

示例一：

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

示例二:

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

思路介绍

思路一-遍历链表

没做过这道题的人最先想到的一定是：先遍历整个链表，算出元素个数，在从头开始寻找中间节点

1. 计算元素个数
2. 找到中间节点

struct ListNode* middleNode(struct ListNode* head) 
{
    //防止传入空指针
    if (head == NULL)
    {
        return NULL;
    }

    //计算链表元素个数
    int count = 0;
    struct ListNode* tail = head;
    while (tail != NULL)
    {
        count++;
        tail = tail->next;
    }

    //找到中间节点
    tail = head;
    count = count / 2;
    for (int i = 0; i < count; i++)
    {
        tail = tail->next;
    }

    return tail;
}

思路二-快慢指针

快慢指针的思路十分经典，使用与很多题目
简单来说，就是定义两个指针，快指针fast和慢指针slow，fast一次走两步，slow一次走一步，fast和slow同时在head出开始走，直到fast走到最后一个节点(链表有奇数个节点)或空指针(链表有偶数个节点)
1. 先来看奇数个节点（这是动图）：

可以得到，当链表元素个数为奇数个节点时，结束条件为fast->next == NULL,此时，中间节点就是slow

2. 再来看偶数个节点（这是动图）：

可以得到，当链表元素个数为偶数个节点时，结束条件为fast == NULL，此时，中间节点就是slow

struct ListNode* middleNode(struct ListNode* head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;

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

    return slow;
}