【链表OJ 3】链表的中间结点-Toy模板网

这篇具有很好参考价值的文章主要介绍了【链表OJ 3】链表的中间结点。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言:

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

一.链表的中间结点

1.1原理:快慢指针的使用

链表元素个数为奇数时

链表元素个数为偶数时

1.2循环条件问题?

一.链表的中间结点

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

题目:

【链表OJ 3】链表的中间结点,C--数据结构刷题,算法,数据结构,c语言,笔记,vscode,开发语言

1.1原理:快慢指针的使用

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

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

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

整体思路:

函数以指向链表头部的指针作为参数。
初始化两个指针 slow 和 fast，它们都指向链表的头部。
进入一个循环，只要fast不为NULL且fast->next不为NULL，循环会继续执行。这个循环用于通过链表前进指针。
每次循环迭代中,slow 指针向前移动一步，通过赋值slow = slow-> next。
fast指针向前移动两步，通过赋值fast = fast -> next -> next。
当循环结束时，slow 指针将指向链表的中间节点。这是因为fast指针的移动速度是slow指针的两倍，当 fast指针到达链表尾部时，slow指针刚好在链表的中间。
最后，函数返回slow指针，即链表的中间节点。

链表元素个数为奇数时

动图演示:

链表元素个数为偶数时

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

【链表OJ 3】链表的中间结点,C--数据结构刷题,算法,数据结构,c语言,笔记,vscode,开发语言

动图演示:

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

代码执行:

【链表OJ 3】链表的中间结点,C--数据结构刷题,算法,数据结构,c语言,笔记,vscode,开发语言