题目

题目地址：

https://leetcode-cn.com/problems/middle-of-the-linked-list/

题目描述：

给定一个带有头结点 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 之间。

相关题目

思路

遍历两次

快慢指针

测试用例

• 边界条件

程序

https://leetcode-cn.com/problems/middle-of-the-linked-list/solution/kuai-man-zhi-zhen-zhu-yao-zai-yu-diao-shi-by-liwei/

遍历两次

• 时间复杂度：O(N)，其中 N是给定链表中的结点数目。
  
• 空间复杂度：O(1)，只需要常数空间存放变量和指针。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        if not head:
            return None
        num = 0
        temp = head
        while temp:
            num += 1
            temp = temp.next
        index = num // 2 + 1
        num = 0
        while head:            
            num += 1
            if num == index:
                return head
            head = head.next

快慢指针

• 时间复杂度：O(N)，其中 N 是给定链表的结点数目。
  
• 空间复杂度：O(1)，只需要常数空间存放 slow 和 fast 两个指针。
  ```python

  Definition for singly-linked list.

  class ListNode:

  def init(self, x):

  self.val = x

  self.next = None

class Solution: def middleNode(self, head: ListNode) -> ListNode: if not head: return None slow, fast = head, head while fast and fast.next: # 判断 fast 和 fast.next 是否存在 slow = slow.next fast = fast.next.next return slow ```