189 8069 5689
本篇内容介绍了“LeetCode题解之怎么求链表的中间结点”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
创新互联专注于新城企业网站建设,成都响应式网站建设公司,商城开发。新城网站建设公司,为新城等地区提供建站服务。全流程按需求定制设计，专业设计，全程项目跟踪，创新互联专业和态度为您提供的服务
题目：求链表的中间结点
给定一个头结点为 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，我们返回第二个结点。
解法一
题目意思还是比较简单的，就是找到中间结点。
首先想到的就是先算出来链表总长度，然后再遍历到中间结点就可以了：
public ListNode middleNode(ListNode head) { int n = 0; ListNode cur = head; while (cur != null) { n++; cur = cur.next; } int k = 0; cur = head; while (k < n / 2) { k++; cur = cur.next; } return cur; }时间复杂度
一共遍历了1次加半次。去除常量，时间复杂度为O(n)
空间复杂度
只用到单独的一个链表结点，空间复杂度为O(1)
解法二
还记得上一篇我们说到的找到结尾第n个结点算法题吗?其中用到了一个叫做快慢指针的解法。
在这里依然可以用到。可能你就有疑惑了，上一次是知道两个指针之间相隔n个结点，这一次怎么用呢?
如果我们将慢指针每次移动一格，快指针每次移动两格，那么快指针是不是每次都是慢指针的两倍步数呢?
这样当快指针移到尾部的时候，慢指针就刚好在中间结点了。
public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }这里因为每次fast都要移动两步，所以需要判断当前结点和下一个结点是否都为空。
slow 1 2 3 4 5 6 fast 1 3 5 7 9 11
上面的例子就是快慢指针会走到的节点数：
如果链表为奇数，比如[1,2,3,4,5]，那么刚好快慢结点就会走到3和5。
如果链表为奇数，比如[1,2,3,4,5,6]，那么刚好快慢结点就会走到4和null。
“LeetCode题解之怎么求链表的中间结点”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！