Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Middle of the Linked List

Middle of the Linked List

Master this topic with zero to advance depth.

Middle of the Linked List

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.

Visual Representation

List: 1 -> 2 -> 3 -> 4 -> 5 Slow moves 1 step, Fast moves 2 steps. Start: Slow=1, Fast=1 Step 1: Slow=2, Fast=3 Step 2: Slow=3, Fast=5 Result: 3 is middle node.
Easy

Examples

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

Level I: Brute Force (Array)

Intuition

Convert the linked list into an array. Then, return the node at index size / 2.

⏱ O(N)💾 O(N)

Detailed Dry Run

List: 1->2->3. Array: [1, 2, 3]. Middle index 3/2 = 1. Array[1] = 2.

java
public ListNode middleNode(ListNode head) {
    List<ListNode> nodes = new ArrayList<>();
    while (head != null) {
        nodes.add(head);
        head = head.next;
    }
    return nodes.get(nodes.size() / 2);
}

⚠️ Common Pitfalls & Tips

O(N) space is not optimal.

Visual Mapping

List: A -> B -> C -> D Array: [A, B, C, D] Size: 4 Middle: size/2 = 2 Result: Array[2] = C
Approach 2

Level II: Two Pass (Length Calculation)

Intuition

First, traverse the list to find the total number of nodes (N). Then, traverse a second time for N/2 steps to reach the middle node.

⏱ O(N)💾 O(1)

Detailed Dry Run

List: 1->2->3->4.

  1. Pass 1: Count = 4.
  2. Target index = 4/2 = 2.
  3. Pass 2: Move to index 2 (node with value 3).
java
public ListNode middleNode(ListNode head) {
    int length = 0;
    ListNode curr = head;
    while (curr != null) { length++; curr = curr.next; }
    curr = head;
    for (int i = 0; i < length / 2; i++) { curr = curr.next; }
    return curr;
}

⚠️ Common Pitfalls & Tips

Ensure the loop runs exactly length/2 times to handle both even and odd lengths correctly.

Approach 3

Level III: Optimal (Two Pointers - Fast & Slow)

Intuition

Use two pointers, slow and fast. Move slow one step at a time and fast two steps at a time. When fast reaches the end, slow will be at the middle.

⏱ O(N)💾 O(1)

Detailed Dry Run

1->2->3->4->5.

  1. S=1, F=1.
  2. S=2, F=3.
  3. S=3, F=5. F.next is null, return S=3.
java
public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

⚠️ Common Pitfalls & Tips

For even length lists, ensure the second middle node is returned (this implementation does that).

← Previous QuestionReverse Linked List
Next Question →Reorder List