876. 链表的中间结点

leetcode

题目描述

876. 链表的中间结点 给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3 。 示例 2：

输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

链表的结点数范围是 [1, 100] 1 <= Node.val <= 100

解题思路

法1

双指针:

定义两个指针,一个指向尾节点,一个指向中间节点,

循环遍历列表,尾节点一次移动两个位置,中间节点一次移动一个位置,中间就节点就是头节点到位节点的中间位置

直到尾节点为空时,返回中间节点的数值就是需要的答案

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

我们使用两个指针slow和fast，初始时都指向链表的头结点head。

快指针fast每次移动两个节点，慢指针slow每次移动一个节点。

当快指针fast到达链表的尾部时，慢指针slow就会指向链表的中间节点。

func middleNode(head *ListNode) *ListNode {
 if head == nil || head.Next == nil {
  return head
 }

 slow := head
 fast := head

 for fast != nil && fast.Next != nil {
  slow = slow.Next
  fast = fast.Next.Next
 }

 return slow
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.9 MB , 在所有 Go 提交中击败了 90.25% 的用户 通过测试用例： 36 / 36 炫耀一下: