BL
U

59. Find Middle Node of Linked List

Easy

Problem Description

Given a singly linked list of NN integers, return the value of the middle node using slow and fast pointers. If there are two middle nodes (even length), return the second middle node.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers.

Output Format

Print the integer value of the middle node.

Example 1:
Input:
5
1 2 3 4 5
Output:
3
Explanation: Middle of 5 nodes is the 3rd node with value 3.
Example 2:
Input:
6
1 2 3 4 5 6
Output:
4
Explanation: Even length: two middles are 3 and 4; second middle is 4.
Example 3:
Input:
1
10
Output:
10
Explanation: Single node is its own middle.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online