Log inSign up
easyLeetCodeNot Started

Middle of the Linked List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

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 · Odd Length List:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3 with value 3.

Example 2 · Even Length List:

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 (node 4).

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 2x fast-and-slow pointer ratio for finding midpoints in linear data structures.
  • Handle parity for both odd and even length lists seamlessly.
  • Eliminate redundant passes over linked memory.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding midpoint, median, or split point of a linked list in a single pass.
  • Splitting linked list for Merge Sort or Palindrome checking.
  • Constraint to avoid counting length in advance.

Algorithmic Decision Tree:

  • If allowed extra memory, store node pointers in an array and index arr[len / 2].
  • For optimal O(1) space, run Fast (2x) and Slow (1x) pointers with condition while (fast != null && fast.next != null).

Connected Patterns:

Palindrome Linked ListReorder ListSort List

1. Brute Force — Array Storage & Direct Index Lookup

Intuition

Read all node pointers into an array. Access index length / 2 in O(1) time.

Algorithm

  1. Step 1: Create an array nodes = [].
  2. Step 2: Traverse curr = head, pushing curr to nodes.
  3. Step 3: Return nodes[nodes.length / 2].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 ListNode* middleNode(ListNode* head) {
15 vector<ListNode*> nodes;
16 while (head) {
17 nodes.push_back(head);
18 head = head->next;
19 }
20 return nodes[nodes.size() / 2];
21 }
22};
23
24int main() {
25 ListNode* h = new ListNode(1);
26 h->next = new ListNode(2);
27 h->next->next = new ListNode(3);
28 h->next->next->next = new ListNode(4);
29 h->next->next->next->next = new ListNode(5);
30
31 Solution sol;
32 ListNode* mid = sol.middleNode(h);
33 cout << "Brute Force Middle: " << (mid ? mid->val : -1) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N) — Traverses the list of N nodes and inserts into an array in O(N).
  • Space complexity: O(N) — Allocates array buffer storing N node pointers.

Why Brute Force Doesn't Scale:

Storing all nodes in an array incurs O(N) memory allocation.

For N = 1,000,000 nodes, fast/slow pointer traversal finishes in ~2ms with 0 bytes extra heap.

2. Better — Two-Pass Length Counting

Intuition

Count the total number of nodes in the list N. Then reset pointer to head and advance N / 2 times.

Algorithm

  1. Step 1: Traverse curr = head, count total length count = 0.
  2. Step 2: Calculate midIdx = count / 2.
  3. Step 3: Reset curr = head.
  4. Step 4: Step forward midIdx times: curr = curr.next.
  5. Step 5: Return curr.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode* middleNode(ListNode* head) {
14 int count = 0;
15 ListNode* curr = head;
16 while (curr) {
17 count++;
18 curr = curr->next;
19 }
20
21 curr = head;
22 for (int i = 0; i < count / 2; ++i) {
23 curr = curr->next;
24 }
25 return curr;
26 }
27};
28
29int main() {
30 ListNode* h = new ListNode(1);
31 h->next = new ListNode(2);
32 h->next->next = new ListNode(3);
33 h->next->next->next = new ListNode(4);
34 h->next->next->next->next = new ListNode(5);
35
36 Solution sol;
37 ListNode* mid = sol.middleNode(h);
38 cout << "Two-Pass Middle: " << (mid ? mid->val : -1) << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N) — Pass 1 counts N nodes. Pass 2 advances N/2 nodes. Total operations = 1.5 * N.
  • Space complexity: O(1) — Uses only integer count and pointer in O(1) space.

3. Optimal — Fast and Slow Pointers (Tortoise and Hare)

Intuition

Move slow by 1 node and fast by 2 nodes at each step. By the time fast hits null or fast.next == null, slow has traversed half the total distance and is positioned exactly at the middle node (or second middle node for even lengths).

Algorithm

  1. Step 1: Initialize slow = head and fast = head.
  2. Step 2: While fast != null && fast.next != null:
  3. a. Advance slow = slow.next.
  4. b. Advance fast = fast.next.next.
  5. Step 3: Return slow.

Middle of the Linked List Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Iteration 1 starts
Visual state
Values and pointers at this exact step
linked list
slow → 1fast → 1
Node 1
1
Node 2
2
Node 3
3
Node 4
4
Node 5
5
NULL
Check / comparison
fast != null && fast.next != null
Decision / next transition
Step forward
Why this step matters

Iteration 1 starts.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode* middleNode(ListNode* head) {
14 ListNode* slow = head;
15 ListNode* fast = head;
16
17 while (fast && fast->next) {
18 slow = slow->next;
19 fast = fast->next->next;
20 }
21
22 return slow;
23 }
24};
25
26int main() {
27 ListNode* h = new ListNode(1);
28 h->next = new ListNode(2);
29 h->next->next = new ListNode(3);
30 h->next->next->next = new ListNode(4);
31 h->next->next->next->next = new ListNode(5);
32 h->next->next->next->next->next = new ListNode(6);
33
34 Solution sol;
35 ListNode* mid = sol.middleNode(h);
36 cout << "Optimal Middle (Even List): " << (mid ? mid->val : -1) << endl; // 4
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N) — Traverses the list in a single pass of exactly N/2 iterations. Strictly optimal linear time.
  • Space complexity: O(1) — Uses exactly two pointer references (slow and fast) with zero auxiliary memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Array Storage & Direct Index LookupO(N)O(N)Traverse the linked list and push every node reference into a dynamic array. Return arr[arr.length / 2].Memory allocation.
2.Better — Two-Pass Length CountingO(N)O(1)In pass 1, count total length N. In pass 2, traverse N / 2 steps from the head and return the resulting node.Two separate passes over the list.
3.Optimal — Fast and Slow Pointers (Tortoise and Hare)OptimalO(N)O(1)Initialize slow = head and fast = head. Advance slow = slow.next and fast = fast.next.next until fast == null || fast.next == null. Return slow.Optimal.

Common Pitfalls & Crucial Edge Cases

Checking only `fast != null`

Calling fast.next.next when fast.next == null causes a NullPointerException on odd-length lists.

Returning first middle instead of second middle

Initializing fast = head.next finds the first middle, whereas initializing fast = head finds the second middle as required by LeetCode.

Crucial Edge Cases to Validate:

  • Single Node — head = [1] -> loop does not execute -> returns node 1.
  • Two Nodes (Even) — head = [1, 2] -> iteration 1 advances slow to 2, fast to null -> returns second node 2.
  • Odd Length — head = [1, 2, 3] -> returns exact middle node 2.
  • Even Length — head = [1, 2, 3, 4] -> returns second middle node 3.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the pointer invariant clearly: 'When fast moves at 2x speed and slow moves at 1x speed, slow is always at floor(distance / 2).'
  2. Emphasize the difference between fast = head (finds second middle) and fast = head.next (finds first middle).
  3. Point out that the loop runs in only N/2 steps.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What happens if you initialize fast = head.next instead of fast = head?

2.What is the exact number of loop iterations for a list of N nodes?

3.Why is the loop condition while (fast != null && fast.next != null) essential?

Back to DSA Sheet