链表的中间结点

2025/2/14 5:05:52 来源：https://blog.csdn.net/2402_87779153/article/details/145124186 浏览: 次关键词：链表的中间结点

文章目录

链表的中间结点
- 题目链接：[在线OJ](https://leetcode.cn/problems/middle-of-the-linked-list/description/)
- 题目详解：
- - 思路1：
  - - 时间复杂度
  - 思路2：
  - - 代码实现
    - 时间复杂度
- 结语

欢迎大家来到我的博客，给生活来点impetus
让我们进入《题海探骊》，感受算法之美！！

链表的中间结点

题目链接：在线OJ

题目详解：

在这里插入图片描述

思路1：

这里我们来说明一下思路1：在这里插入图片描述

int i=0;//计数器的作用
while(pcur)
{pcur=pcur->next;i++;
}

接下里修改判断条件即可。

时间复杂度

既然这里存在两个循环，那时间复杂度到底是否是O（n^2）呢？

答案是否定的，这两个循环并不存在循环的嵌套，这两个循环是分开的，这里的时间复杂度是O（n）。

思路2：

思路1用代码表示还是比较麻烦，这里我们来看看思路2：快慢指针。
我们首先定义两个指针为fast和slow。
在这里插入图片描述
这里是两种情况，所以这里只要是fast->next=NULL或者fast=NULL退出循环即可，真的是这样吗？
如果写成

while(fast=NULL||fast->next=NULL)
{//
}

这样就会陷入死循环，所以这里应该是逻辑与。
写好代码一定要及时检验。

代码实现

typedef struct ListNode ListNode;//重定义为了书写方便
struct ListNode* middleNode(struct ListNode* head) {ListNode*slow,*fast;slow=fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}

细节：请问这里是否能写成
while(fast->next=NULL&&fast=NULL)
其实就是将判决条件交换个位置，请问这样可以吗？
我们不妨来验证验证。先执行fast->next=NULL如果是偶数个结点就会对NULL解引用

那么为什么不交换位置就可以呢？
答案是短路，因为不交换位置时fast=NULL为假，逻辑与，有一个为假全为假，无论后面有多少个判决调教都不会执行了