【C语言】Leetcode 876. 链表的中间节点

题目

通过题目的要求可以判断出有两种示例要解决，一种是偶数节点的链表，一种是奇数节点的链表，应对这两种情况我们需要使程序对二者都可以兼容。

解决思路

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

中间节点，只要找到中间的位置就能找到中间的节点。那么这个位置要怎么去查找呢？

我们可以用快慢指针的思想来进行查找，定义一个慢指针，再定义一个是慢指针速度二倍的快指针，这样的话当快指针到最后的位置的时候慢指针指向的就是中间节点了。

但是在查找的时候还要同时解决上面提到的两种情况：

①奇数链表

从两个指针的初始开始研究，当前两个指针都处在第一个节点的位置，然后我们开始移动。

可以发现，在奇数数量节点的链表中，当fast到达最后一个节点的时候slow刚好指向了中间节点。这样就完成了查找中间节点的目的，该遍历循环的条件是fast -> next ！= NULL，也就是当fast的next是NULL的时候终止循环，此时的slow指向就是中间节点。

②偶数链表

同样的，我们也是从头开始循环。

因为是偶数链表，所以需要查找到的中间节点的位置是中间两个节点中的第二个，当循环后发现，当fast到达NULL的时候slow指向的才是中间的第二个节点，所以该情况的循环条件为fast ！= NULL。