Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second middle node.

Examples

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: Two middle nodes (3 and 4), return the second one.

Constraints

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

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Iterative pointer walk (this problem) O(n) O(1) Traversal, insertion
Dummy head node O(n) O(1) Simplify head-edge cases
Reversal (3-pointer) O(n) O(1) Reverse sublist or full list
Slow/fast pointers O(n) O(1) Middle, cycle, merge lists

Thinking Process

Slow & Fast Pointer

Move slow one step and fast two steps at a time. When fast reaches the end, slow is at the middle.

Why it works: fast travels at 2x speed. When fast has covered the full list, slow has covered exactly half.

Odd vs Even Length

Odd (5 nodes):   1 → 2 → 3 → 4 → 5
                          ↑ slow stops here (fast at 5, fast->next is null)

Even (6 nodes):  1 → 2 → 3 → 4 → 5 → 6
                              ↑ slow stops here (fast at null)

For even-length lists, this naturally returns the second middle node, matching the problem requirement.

Linked list: pointer walk 1 2 3 slow → → fast (2x speed)

Approach: Slow & Fast Pointer – O(n)

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

Solution Explanation

Approach: Iterative pointer walk (this problem)

Key idea: ### Slow & Fast Pointer

How the code works: Why it works: fast travels at 2x speed. When fast has covered the full list, slow has covered exactly half.

Walkthrough — input head = [1,2,3,4,5], expected output [3,4,5]:

The middle node is 3.

Common Mistakes

  • Checking only fast->next without checking fast first (null dereference on even-length lists)
  • Returning the first middle for even-length lists (this problem wants the second)

Key Takeaways

  • Slow/fast pointer is the fundamental linked list technique – finding the middle in one pass without knowing the length
  • The loop condition while (fast && fast->next) handles both odd and even lengths
  • This is a building block for more complex problems: merge sort on linked lists needs the middle, and cycle detection uses the same two-pointer idea

References

Template Reference