Middle of the Linked List
🇷🇺 Название: Середина связанного списка
LeetCode: middle-of-the-linked-list
Временная сложность: O(n)
Пространственная сложность: O(1)
Решение¶
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow_pointer = head
fast_pointer = head
while fast_pointer is not None and fast_pointer.next is not None:
slow_pointer = slow_pointer.next
fast_pointer = fast_pointer.next.next
return slow_pointer
🇺🇸 Условие¶
Given the head
of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
🇷🇺 Условие¶
Примеры¶
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
{
"examples": [
{
"input": {
"head": [1,2,3,4,5]
},
"output": [3,4,5]
},
{
"input": {
"head": [1,2,3,4,5,6]
},
"output": [4,5,6]
}
]
}
Ограничения¶
- The number of nodes in the list is in the range
[1, 100]
. - \(1 \leq Node.val \leq 100\)
Потребление ресурсов¶
⏱ Time complexity: O(n)
¶
- Один проход по списку двумя указателями.
fast_pointer
проходит поn
элементам с шагом 2,slow_pointer
— с шагом 1.
Итог: O(n)
🧠 Space complexity: O(1)
¶
- Используются только два указателя (
slow_pointer
,fast_pointer
), независимо от размера списка.
Итог: O(1)
easy linked-list two-pointers
Metadata
- title_rus: Середина связанного списка
- difficulty: Easy
- leetcode_url: https://leetcode.com/problems/middle-of-the-linked-list/
- topics: ['Linked List', 'Two Pointers']
- time: O(n)
- space: O(1)
- grind75: True
- tags: ['Easy', 'Linked List', 'Two Pointers', 'problem']
- git_revision_date_localized: 5 июля 2025 г.
- git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
- git_revision_date_localized_tag:
- git_revision_date_localized_raw_date: 5 июля 2025 г.
- git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
- git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
- git_revision_date_localized_raw_iso_date: 2025-07-05
- git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
- git_revision_date_localized_raw_timeago:
- git_revision_date_localized_raw_custom: 05. июля 2025
- git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
- git_site_revision_date_localized_tag:
- git_site_revision_date_localized: 5 июля 2025 г.
- git_site_revision_date_localized_raw_date: 5 июля 2025 г.
- git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
- git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
- git_site_revision_date_localized_raw_iso_date: 2025-07-05
- git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
- git_site_revision_date_localized_raw_timeago:
- git_site_revision_date_localized_raw_custom: 05. июля 2025