链表的中间结点

欢迎大家来到我的博客，给生活来点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为假，逻辑与，有一个为假全为假，无论后面有多少个判决调教都不会执行了

时间复杂度

这里的时间复杂度也是O（n），但是思路2的代码比思路1的代码会简洁很多，代码执行效率更高。

结语

最后感谢大家的倾听，欢迎有更多的思路在评论区讨论。
世上无难事，只怕有心人，加油！！！陌生人！！