Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Middle of the Linked List

EASYProblemSolveExternal Links

Description

Given the head of a singly linked list, return the middle node of the linked list.

If the list has an odd number of nodes, there is exactly one middle node — return it. If the list has an even number of nodes, there are two middle nodes — return the second of the two.

Returning a node means returning that node and everything after it (the rest of the list from that point onward).

Examples

Example 1

Input: head = [1, 2, 3, 4, 5]

Output: [3, 4, 5]

Explanation: The list has 5 nodes, which is odd. The middle is the 3rd node (1-indexed). Node 3 is at position ⌊5/2⌋ + 1 = 3. We return node 3 along with all nodes after it: [3, 4, 5].

Example 2

Input: head = [1, 2, 3, 4, 5, 6]

Output: [4, 5, 6]

Explanation: The list has 6 nodes, which is even. There are two middle nodes: node 3 and node 4. The problem says to return the second middle node, so we return node 4 and everything after it: [4, 5, 6].

Example 3

Input: head = [1]

Output: [1]

Explanation: A single-node list has exactly one node, which is both the first and the middle. We return that node itself.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward way to find the middle of a linked list is to think about what we would do with an array: if we know the total length, the middle element is at index length / 2 (using integer division).

But unlike an array, a singly linked list doesn't tell us its length upfront. We have to count the nodes ourselves. So the natural two-step approach is:

  1. First pass: Walk through the entire list from head to tail, counting every node to determine the total length.
  2. Second pass: Walk through the list again, but this time stop after exactly length / 2 steps. The node you land on is the middle.

Think of it like measuring a rope: first you stretch it out to see how long it is, then you fold it to find the halfway point.

For even-length lists, integer division of length / 2 naturally gives us the index of the second middle node (0-indexed), which is exactly what the problem asks for.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5]:

Phase 1 — Count the nodes:

Step 1: Start at node 1, count = 1. Move to next.

Step 2: At node 2, count = 2. Move to next.

Step 3: At node 3, count = 3. Move to next.

Step 4: At node 4, count = 4. Move to next.

Step 5: At node 5, count = 5. Next is null. Total count = 5.

Phase 2 — Walk to the middle:

Step 6: Compute mid = count / 2 = 5 / 2 = 2 (integer division). We need to advance 2 steps from head.

Step 7: Start at node 1. Advance once → node 2. Advance again → node 3.

Step 8: We've taken 2 steps. We are at node 3. Return this node. The middle of [1, 2, 3, 4, 5] is node 3.

Two-Pass Approach — Count Then Navigate to Middle — Watch how we first count all nodes to determine the list length, then traverse again to the exact middle position.

Algorithm

  1. Initialize count = 0 and a pointer temp = head
  2. First pass: Traverse the entire list, incrementing count for each node. When temp becomes null, count holds the total number of nodes.
  3. Compute mid = count / 2 (integer division)
  4. Second pass: Reset temp = head. Advance temp exactly mid times by following next pointers.
  5. Return temp — it now points to the middle node

Code

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        // First pass: count total nodes
        int count = 0;
        ListNode* temp = head;
        while (temp != nullptr) {
            count++;
            temp = temp->next;
        }
        
        // Second pass: advance to middle
        int mid = count / 2;
        temp = head;
        while (mid > 0) {
            temp = temp->next;
            mid--;
        }
        
        return temp;
    }
};
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # First pass: count total nodes
        count = 0
        temp = head
        while temp is not None:
            count += 1
            temp = temp.next
        
        # Second pass: advance to middle
        mid = count // 2
        temp = head
        for _ in range(mid):
            temp = temp.next
        
        return temp
class Solution {
    public ListNode middleNode(ListNode head) {
        // First pass: count total nodes
        int count = 0;
        ListNode temp = head;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        
        // Second pass: advance to middle
        int mid = count / 2;
        temp = head;
        while (mid > 0) {
            temp = temp.next;
            mid--;
        }
        
        return temp;
    }
}

Complexity Analysis

Time Complexity: O(n)

The first pass visits all n nodes to count them. The second pass visits n/2 nodes to reach the middle. Total traversal: n + n/2 = 3n/2, which simplifies to O(n).

Space Complexity: O(1)

We only use a counter variable and a temporary pointer, both of which are constant regardless of list size.

Why This Approach Is Not Efficient

While the brute force runs in O(n) time and O(1) space — which is already optimal in Big-O terms — it requires two separate passes through the linked list. The first pass counts nodes and the second navigates to the middle.

In practice, needing two passes means:

  • We visit approximately 1.5n nodes total instead of n
  • In scenarios where the list is streamed or can only be traversed once (a common interview constraint), this approach would fail entirely

The key insight is: can we find the middle in a single pass? If one pointer moves at speed 1 and another moves at speed 2, by the time the faster pointer reaches the end, the slower pointer will be exactly at the middle. This is the famous Tortoise and Hare (slow and fast pointer) technique, and it finds the middle in exactly one traversal.

Optimal Approach - Slow and Fast Pointers (Tortoise and Hare)

Intuition

Imagine two runners on a straight track of unknown length. Both start at the starting line. Runner A (the "tortoise") takes one step at a time. Runner B (the "hare") takes two steps at a time.

When Runner B reaches the finish line, how far has Runner A gone? Exactly half the track — because Runner B covered twice the distance in the same number of moves.

We apply this exact principle to the linked list:

  • Slow pointer advances one node at a time: slow = slow.next
  • Fast pointer advances two nodes at a time: fast = fast.next.next
  • We keep advancing both until the fast pointer reaches the end (null) or runs out of nodes to jump to

At that moment, the slow pointer is sitting right at the middle node.

Why does this work for even-length lists? When the list has even nodes, the fast pointer will land exactly on the last node (where fast.next is null). At that point, slow has advanced exactly n/2 steps from the head, landing on the second middle node — which is exactly what the problem asks for.

This is one of the most elegant techniques in linked list problems and appears as a building block in cycle detection, finding the start of a cycle, and palindrome checking.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5]:

Step 1: Initialize both slow and fast at head (node 1). Both pointers start at the same position.

Step 2: Check loop condition: fast is not null AND fast.next is not null. fast = node 1, fast.next = node 2. Condition is true — enter the loop.

Step 3: Move slow one step: slow goes from node 1 → node 2. Move fast two steps: fast goes from node 1 → node 2 → node 3.

Step 4: Check loop condition again: fast = node 3, fast.next = node 4. Condition is true — continue.

Step 5: Move slow one step: slow goes from node 2 → node 3. Move fast two steps: fast goes from node 3 → node 4 → node 5.

Step 6: Check loop condition: fast = node 5, fast.next = null. Condition is false — fast.next is null, so we stop the loop.

Step 7: Return slow, which points to node 3. The middle of [1, 2, 3, 4, 5] is node 3. We found it in a single pass!

Now let's verify with an even-length list: head = [1, 2, 3, 4, 5, 6]:

  • Start: slow = 1, fast = 1
  • After iteration 1: slow = 2, fast = 3
  • After iteration 2: slow = 3, fast = 5
  • After iteration 3: slow = 4, fast = null (fast went from 5 → 6 → null, but we first check fast.next which is 6, then move)
  • Actually: fast = 5, fast.next = 6, so we enter loop. slow → 4, fast → 5 → 6 → null? No, fast = fast.next.next = 6.next... wait. Let me be precise:
  • Iteration 3: fast = 5, fast.next = 6 (not null), enter loop. slow = slow.next = 4. fast = fast.next.next = node 6.next = null? No. fast.next = 6, fast.next.next = null. So fast = null. But wait — we moved. Now fast = null.
  • Check condition: fast is null → stop loop. slow = 4. Return node 4 — the second middle node. Correct!

Tortoise and Hare — Finding Middle in One Pass — Watch how the slow pointer (tortoise) moves one step while the fast pointer (hare) moves two steps. When fast reaches the end, slow is at the middle.

Algorithm

  1. Initialize two pointers: slow = head, fast = head
  2. While fast is not null AND fast.next is not null:
    a. Move slow one step forward: slow = slow.next
    b. Move fast two steps forward: fast = fast.next.next
  3. When the loop ends, slow is at the middle node
  4. Return slow

Code

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return slow;
    }
};
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        
        return slow
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
}

Complexity Analysis

Time Complexity: O(n)

The fast pointer traverses the entire list (n nodes, 2 at a time), so the loop runs n/2 times. Each iteration does constant work (two pointer advances). Total time: O(n/2) = O(n).

Although both approaches are O(n), the single-pass approach visits approximately n/2 + n = 1.5n node accesses in total (slow visits n/2, fast visits n), compared to 1.5n for brute force. The real advantage is needing only one traversal — important for streaming or single-pass constraints.

Space Complexity: O(1)

We use only two pointer variables (slow and fast). No additional data structures are needed regardless of the list size.