前言: 

        本文收录于http://t.csdn.cn/n6UEP数据结构刷题的博客中,首先欢迎大家的来访，其次如有错误，非常欢迎大家的指正！我会及时更正错误！

目录

一.链表的中间结点 

1.1原理:快慢指针的使用

链表元素个数为奇数时

链表元素个数为偶数时

1.2循环条件问题?

---

一.链表的中间结点 

来源:876. 链表的中间结点 - 力扣（LeetCode）

题目:

1.1原理:快慢指针的使用

这个算法之所以有效，是因为fast指针的移动速度是slow指针的两倍。

快慢指针的精妙之处在于,当快指针移动到链表尾部时,慢指针就刚好移动了链表长度的一半,从而找到中间节点。因此当,fast指针到达链表尾部时，slow指针将正好指向链表的中间节点。无论链表长度奇偶,这个方法都可以在一次遍历正确找到中间节点。

时间复杂度:O(n),因为只遍历链表一次。
空间复杂度:O(1),因为没有使用额外的空间。

整体思路:

1. 函数以指向链表头部的指针作为参数。

2. 初始化两个指针 slow 和 fast，它们都指向链表的头部。

3. 进入一个循环，只要fast不为NULL且fast->next不为NULL，循环会继续执行。这个循环用于通过链表前进指针。

4. 每次循环迭代中,slow 指针向前移动一步，通过赋值slow = slow-> next。

5. fast指针向前移动两步，通过赋值fast = fast -> next -> next。

6. 当循环结束时，slow 指针将指向链表的中间节点。这是因为fast指针的移动速度是slow指针的两倍，当 fast指针到达链表尾部时，slow指针刚好在链表的中间。

7. 最后，函数返回slow指针，即链表的中间节点。

链表元素个数为奇数时

动图演示:

链表元素个数为偶数时

返回第二个中间结点的原因是题目要求:

 动图演示:

1.2循环条件问题?

while 循环条件 fast && fast->next 的目的是为了确保在遍历链表时不会出现空指针异常。

如果 while 循环的条件只是 fast，而不考虑 fast->next，那么在链表长度为奇数时,fast->next为 NULL，此时 fast 的下一次迭代会导致空指针异常。因此，为了避免这种情况，需要同时判断   fast 和 fast->next 是否为 NULL，只有两者都不为 NULL 时，才能继续进行循环。

代码实现:

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;
}

代码执行:

        本文到此结束，如有错误欢迎大家指正，感谢来访！