【链表OJ 3】链表的中间结点

一.链表的中间结点

来源: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 不能写成 fast->next && fast 的目的是为了确保在遍历链表时不会出现空指针异常。

如果将循环条件调换为fast->next&& fast ，在链表长度为奇数时，当快指针 fast指向最后一个节点时，fast->next仍然不为NULL，但此时fast已经为NULL，这样会导致在访问fast的next指针时出现错误。

通过保持条件为fast && fast->next ，可以确保在fast 和 fast->next 每次迭代中，快指针都不为NULL，从而避免了空指针的访问错误。这是正确处理快慢指针遍历的关键。

因此，为了保证代码的正确性，应该保持原始代码中的循环条件不变，即fast && fast->next。

代码实现

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

代码执行:

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