leecode 刷题（32）-- 链表的中间节点
leecode 刷题（32）-- 链表的中间节点
描述：
给定一个带有头结点 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，我们返回第二个结点。提示：
给定链表的结点数介于 1 和 100 之间。
思路：
做这道题有两种思路：
- 先遍历一遍整个链表，按顺序将每个节点放入数组 A 中，我们可以通过索引检索每个结点，那么中间节点就是
A[A.Length/2]。 - 快慢指针法：设置两个指针：slow 和 fast，快指针速度是慢指针的两倍，遍历单链表，当 fast 指针到达链表的末尾时，slow 指针刚好在中间。
时间复杂度两种方法都需遍历一遍链表，都是 O(N) ，空间复杂度第一种方法为 O(N)，第二种方法为 O(1)， 明显快慢指针法更为高效。
代码如下：
这里仅给出快慢指针法的代码：
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}总结：
快慢指针法来解决单链表问题是一种很好的方法，之前我们也有写过一道跟该题类似的题目，也是采用快慢指针法来解决，即：
leecode原题：
链表的中间结点
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-07-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
