Problem statement

Given the head of a non-empty singly linked list, return its middle node — the list from that node to the end is what gets printed.

When the list has two middle nodes (an even number of nodes), return the second one.

Example 1

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node is 3.

Example 2

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: 3 and 4 are both middle nodes; the second one, 4, is returned.

Example 3

Input: head = [7]
Output: [7]

Constraints

• The number of nodes in the list is in the range [1, 100]
• 1 <= Node.val <= 100

Hints for Middle of the Linked List

1. Hint 1

   Counting the nodes first and then walking half way works in two passes.

2. Hint 2

   Can one pass do it? Move one pointer one step at a time and another two steps at a time.

3. Hint 3

   When the fast pointer cannot take two more steps (it is null, or its next is null), the slow pointer is on the (second) middle node.

How to solve Middle of the Linked List

A pointer moving at twice the speed reaches the end exactly when the slower one reaches the middle.

Approach

1. Set slow = fast = head.
2. While fast and fast.next are not null: slow = slow.next, fast = fast.next.next.
3. Return slow.

Why it works

After k iterations slow is at index k and fast at index 2k. The loop stops at the first k with 2k >= n - 1, i.e. k = floor(n / 2) — the middle for odd n and the second middle for even n.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Testing fast.next.next instead of fast.next in the loop condition returns the first middle on even lengths.
• Check fast before fast.next to avoid dereferencing null.

Reference solution

Python

from typing import Optional

def middleNode(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Java

public static ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

C++

ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

JavaScript

var middleNode = function(head) {
    var slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More two pointers problems

• Nth Node From End of Linked List Easy
• Intersection of Two Sorted Linked Lists Easy
• Palindrome Linked List Easy
• Remove Duplicates from Sorted List Easy
• Merge Two Sorted Lists Easy
• Two Sum IV - Input is a BST Easy