题目概述(简单难度)
给定一个头结点为 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。
(测评系统对该结点序列化表述是 [3,4,5])。 注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val =3, ans.next.val = 4, ans.next.next.val = 5,
以及 ans.next.next.next =NULL.
示例 2:
输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和4,我们返回第二个结点。
附上leetcode链接:
点击此处进入leetcode
思路与代码
思路展现
思路一
这道题最朴素的做法是,先遍历一次,计算链表的长度,进而计算链表中间结点的下标(注意当链表个数为偶数的时候,长度除2得到的值是中间的第二个结点的下标),此时需要再遍历一次,才能来到所要求结点的位置。
缺点:
必须先遍历完整个链表,然后才可以「干正事」,再遍历到一半,找到中间结点;
在链表的长度很长的时候,这种方法之前的等待会很久
思路二
也是这道题目所延申出来的最经典的解题方法:快慢指针
快慢指针的思路其实非常经典,运用到的场景也非常多,就拿这个题目我们来分析下如何拿快慢指针的思路来解题
首先在找一个链表的中间节点前,我们首先要判断这个链表的个数是奇数还是偶数,因为不同的个数,其中间节点也各不相同
快慢指针的思路是:使用两个指针变量fast和slow,fast代表快指针,slow代表慢指针,刚开始都位于链表的第 1 个结点,slow指针永远一次只走 1 步,fast指针永远一次只走 2 步,fast指针在前,slow指针在后,同时走。
下面我们先来看奇数节点的链表:
我们会发现当fast指针走到了奇数个节点链表的尾节点的时候,slow指针所指向的节点即为中间节点.所以放到程序中的逻辑为当fast.next=null的时候,slow所指向的节点即为中间节点.
下面我们来看偶数节点的链表
思路如同奇数链表一样,但结果不同的是,当fast=null的时候,我们slow指针所指向的节点才是我们的中间节点.
综合上述思路后,下面我们来看代码
代码示例
class Solution { public ListNode middleNode(ListNode head) { ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } return slow; } }
我们来分析一下代码:
1:首先我们定义两个快慢指针fast和slow指向我们的头节点head
2:再来看我们的while循环,此处的while循环也是大有讲究的,需要注意的点有两个:
(1):就是fast!=null必须在fast.next!=null的前面,为什么要这么做呢?
原因是对于奇数个节点的链表而言这个条件都是满足的,不管这两个谁在前都是满足的,逻辑与是两边的表达式都是真才会执行循环体的语句,此时当fast走到最后一个尾节点时,fast.next!=null这个表达式不管在前还是在后,都是假的,所以循环体自然不会执行.
但是对于偶数个节点的链表来说,当fast走到尾节点后时,也就是超过尾节点时,此时fast=null,slow所指向的节点即为我们要找的中间节点,但是当fast.next!=null写在fast!=null的前面后,会发生空指针异常,那么就算找到了中间节点,也会因为发生了空指针异常而无法返回slow所对应的节点.
而fast!=null写在fast.next!=null的前面后,此时对于fast!=null&&fast.next!=null这个式子而言,fast因为等于null,所以逻辑与左边为假,那么逻辑与右边的表达式就不会被执行,尽管此时fast.next!=null这个表达式空指针异常,但是正是因为逻辑与中只要第一个表达式为假,第二个表达式就不会被执行这一原理,所以程序仍然照常运行.
(2):很多小伙伴对于为什么要用逻辑与(&&)纳闷,明明等式两边的表达式是来自于不同情况的节点数总结出来的,按理来说只要满足一个就成,用逻辑或(||)没有毛病啊,只要一个为真就执行循环体,乍一眼一看,逻辑没问题,没毛病,可事实真的是这样吗?我们来分析下:
对于奇数个节点的链表而言,逻辑或是两边的表达式只要有一个为真就会执行循环体的语句,表达式都为假的话循环体就不会被执行,此时当fast走到最后一个尾节点时,fast!=null这个表达式为真,所以循环体继续执行,但是此时slow对应的节点已经是中间节点了,那么再继续往下执行的话,就不再是中间节点了,所以用逻辑或是错误的
对于偶数个节点的链表而言,当fast走到尾节点后时,也就是超过尾节点时,此时fast=null,slow所指向的节点即为我们要找的中间节点,但是对于fast!=null || fast.next!=null这个式子而言,fast因为等于null,所以逻辑或左边表达式为假,右边表达式直接空指针异常,那么就无法跳出循环,所以我们slow所指向的节点还是返回不了.所以用逻辑或是错误的.
总结
1:可以看到虽然此题代码量很少,但是需要注意的细节点非常多,稍不留神代码便会出错.
2:要学会快慢指针这个思路,非常重要.
3:快慢指针算法:
时间复杂度:O(N),其中 N是给定链表的结点数目。
空间复杂度:O(1),只需要常数空间存放 slow 和 fast 两个指针