Middle of the Linked List

🎯

Middle of the Linked List

easyTWO_POINTERAmazonGoogleFacebook

Imagine you are reading a long scroll and want to find the exact middle point to split it evenly without counting every character.

💡 This problem is about finding the middle node of a singly linked list efficiently. Beginners often struggle because linked lists don't allow direct indexing, so you can't just jump to the middle. Understanding how to traverse with two pointers at different speeds is key.

📋

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.

1 ≤ n ≤ 10^5The number of nodes in the list is at least 1Node values can be any integer

💡

Example

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

Output3

The list has 5 nodes, so the middle is the 3rd node with value 3.

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

Output4

The list has 6 nodes, so the middle nodes are 3 and 4; we return the second middle node with value 4.

• Single node list → return that node
• Two node list → return second node
• All nodes have the same value → still return second middle if even length
• Very large list (n=10^5) → solution must be efficient

⚠️

Common Mistakes

Returning the first middle node instead of the second when list length is even

Incorrect node returned, failing test cases

✅ Use the condition 'while fast and fast.next' to ensure slow moves to second middle

Using fast.next.next without checking if fast.next is null

Runtime error due to null pointer dereference

✅ Check both 'fast != null' and 'fast.next != null' before accessing fast.next.next

Modifying the input list nodes accidentally

Unexpected side effects or corrupted list

✅ Only move pointers, do not change node values or next pointers

Not handling single node or two node lists correctly

Incorrect output or errors on small inputs

✅ Test and handle small lists explicitly or ensure loop conditions cover them

🧠

Brute Force (Count then Traverse)

💡 This approach exists because it is the most straightforward way to find the middle: count all nodes first, then traverse again to the middle. It helps beginners understand the problem constraints and why a single pass is better.

Intuition

First, count the total number of nodes in the list. Then, calculate the middle index and traverse again to that node to return it.

Algorithm

1. Initialize a counter to zero and traverse the list to count the total nodes.
2. Calculate the middle index as total_count // 2.
3. Traverse the list again up to the middle index.
4. Return the node at the middle index.

💡 The two traversals make it easy to understand but inefficient. Beginners often find it easier to implement this before optimizing.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def middleNode(head: ListNode) -> ListNode:
    count = 0
    current = head
    while current:
        count += 1
        current = current.next
    mid = count // 2
    current = head
    for _ in range(mid):
        current = current.next
    return current

# Example usage:
# head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
# print(middleNode(head).val)  # Output: 3

Line Notes

count = 0Initialize counter to count nodes

while current:Traverse entire list to count nodes

mid = count // 2Calculate middle index using integer division

for _ in range(mid):Traverse again to the middle node

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public ListNode middleNode(ListNode head) {
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        int mid = count / 2;
        current = head;
        for (int i = 0; i < mid; i++) {
            current = current.next;
        }
        return current;
    }

    // Example main method
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        Solution sol = new Solution();
        System.out.println(sol.middleNode(head).val); // Output: 3
    }
}

Line Notes

int count = 0;Initialize counter for nodes

while (current != null)Traverse list to count nodes

int mid = count / 2;Calculate middle index

for (int i = 0; i < mid; i++)Traverse again to middle node

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int count = 0;
        ListNode* current = head;
        while (current != nullptr) {
            count++;
            current = current->next;
        }
        int mid = count / 2;
        current = head;
        for (int i = 0; i < mid; i++) {
            current = current->next;
        }
        return current;
    }
};

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    Solution sol;
    cout << sol.middleNode(head)->val << endl; // Output: 3
    return 0;
}

Line Notes

int count = 0;Initialize node counter

while (current != nullptr)Count all nodes in list

int mid = count / 2;Compute middle index

for (int i = 0; i < mid; i++)Traverse to middle node

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function middleNode(head) {
    let count = 0;
    let current = head;
    while (current !== null) {
        count++;
        current = current.next;
    }
    let mid = Math.floor(count / 2);
    current = head;
    for (let i = 0; i < mid; i++) {
        current = current.next;
    }
    return current;
}

// Example usage:
// let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
// console.log(middleNode(head).val); // Output: 3

Line Notes

let count = 0;Initialize count of nodes

while (current !== null)Traverse list to count nodes

let mid = Math.floor(count / 2);Calculate middle index

for (let i = 0; i < mid; i++)Traverse again to middle node

⏱

Complexity

TimeO(n) + O(n) = O(n)

SpaceO(1)

We traverse the list twice: once to count nodes and once to reach the middle node, so total time is linear. Space is constant as we only use pointers and counters.

💡 For n=100,000 nodes, this means about 200,000 steps, which is acceptable but not optimal.

Interview Verdict: Accepted but not optimal

This approach works but is inefficient because it requires two passes. Interviewers expect a single-pass solution.

🧠

Two-Pass Using Array Conversion

💡 This approach converts the linked list to an array to leverage direct indexing. It helps beginners understand the limitation of linked lists and the power of arrays, but it uses extra space.

Intuition

Traverse the linked list once to store all nodes in an array, then return the middle element by direct indexing.

Algorithm

1. Initialize an empty array.
2. Traverse the linked list and append each node to the array.
3. Calculate the middle index as length of array // 2.
4. Return the node at the middle index in the array.

💡 This approach is easier to implement but uses extra memory proportional to the list size.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def middleNode(head: ListNode) -> ListNode:
    nodes = []
    current = head
    while current:
        nodes.append(current)
        current = current.next
    return nodes[len(nodes) // 2]

# Example usage:
# head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
# print(middleNode(head).val)  # Output: 3

Line Notes

nodes = []Initialize list to store nodes

while current:Traverse list to append nodes

nodes.append(current)Store current node reference

return nodes[len(nodes) // 2]Return middle node by index

import java.util.ArrayList;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

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

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        Solution sol = new Solution();
        System.out.println(sol.middleNode(head).val); // Output: 3
    }
}

Line Notes

ArrayList<ListNode> nodes = new ArrayList<>();Create dynamic array to store nodes

while (current != null)Traverse list to add nodes

nodes.add(current);Add current node to array

return nodes.get(nodes.size() / 2);Return middle node by index

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> nodes;
        ListNode* current = head;
        while (current != nullptr) {
            nodes.push_back(current);
            current = current->next;
        }
        return nodes[nodes.size() / 2];
    }
};

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    Solution sol;
    cout << sol.middleNode(head)->val << endl; // Output: 3
    return 0;
}

Line Notes

vector<ListNode*> nodes;Create vector to store node pointers

while (current != nullptr)Traverse list to store nodes

nodes.push_back(current);Add current node pointer to vector

return nodes[nodes.size() / 2];Return middle node by index

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function middleNode(head) {
    const nodes = [];
    let current = head;
    while (current !== null) {
        nodes.push(current);
        current = current.next;
    }
    return nodes[Math.floor(nodes.length / 2)];
}

// Example usage:
// let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
// console.log(middleNode(head).val); // Output: 3

Line Notes

const nodes = [];Initialize array to hold nodes

while (current !== null)Traverse list to collect nodes

nodes.push(current);Add current node to array

return nodes[Math.floor(nodes.length / 2)];Return middle node by index

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the list once to build an array, then access the middle node by index. Time is linear but space is also linear due to the array.

💡 For n=100,000, this means 100,000 steps and storing 100,000 nodes in memory, which may be costly.

Interview Verdict: Accepted but uses extra space

This approach is simpler but not space efficient. Interviewers prefer in-place solutions.

🧠

Optimal Single-Pass Two Pointers

💡 This is the classic and optimal approach using two pointers moving at different speeds. It is efficient and elegant, and mastering it is essential for linked list problems.

Intuition

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

Algorithm

1. Initialize two pointers, slow and fast, at the head.
2. Move slow by one node and fast by two nodes in each iteration.
3. Continue until fast reaches the end or fast.next is null.
4. Return the slow pointer as the middle node.

💡 This approach uses a single traversal and no extra space, but understanding the pointer movement is key.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def middleNode(head: ListNode) -> ListNode:
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

# Example usage:
# head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
# print(middleNode(head).val)  # Output: 3

Line Notes

slow = headInitialize slow pointer at head

fast = headInitialize fast pointer at head

while fast and fast.next:Loop until fast reaches end or one before end

slow = slow.nextMove slow pointer one step

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public 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;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        Solution sol = new Solution();
        System.out.println(sol.middleNode(head).val); // Output: 3
    }
}

Line Notes

ListNode slow = head;Initialize slow pointer at head

ListNode fast = head;Initialize fast pointer at head

while (fast != null && fast.next != null)Loop until fast reaches end or one before end

slow = slow.next;Move slow pointer one step

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

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;
    }
};

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    Solution sol;
    cout << sol.middleNode(head)->val << endl; // Output: 3
    return 0;
}

Line Notes

ListNode* slow = head;Initialize slow pointer at head

ListNode* fast = head;Initialize fast pointer at head

while (fast != nullptr && fast->next != nullptr)Loop until fast reaches end or one before end

slow = slow->next;Move slow pointer one step

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function middleNode(head) {
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

// Example usage:
// let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
// console.log(middleNode(head).val); // Output: 3

Line Notes

let slow = head;Initialize slow pointer at head

let fast = head;Initialize fast pointer at head

while (fast !== null && fast.next !== null)Loop until fast reaches end or one before end

slow = slow.next;Move slow pointer one step

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list once with two pointers, so time is linear. Space is constant as we only use two pointers.

💡 For n=100,000, this means about 100,000 steps, which is efficient and scalable.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews due to its efficiency and simplicity.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal two-pointer approach is the best to code in interviews due to its efficiency and simplicity. The brute force and array methods are useful to mention but not to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Count then Traverse)	O(n)	O(1)	No	N/A	Mention only - never code
2. Array Conversion	O(n)	O(n)	No	N/A	Mention only - never code
3. Optimal Two Pointers	O(n)	O(1)	No	N/A	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show your understanding. Next, present the optimal two-pointer solution and code it carefully. Finally, test your code with edge cases.

How to Present

Clarify the problem and confirm input/output format.Describe the brute force approach: count nodes, then traverse again.Explain the limitations of brute force and mention the array approach.Introduce the optimal two-pointer approach and explain the intuition.Write clean code for the two-pointer solution.Test with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your understanding of linked list traversal, pointer manipulation, and ability to optimize from a naive to an efficient solution.

Common Follow-ups

• What if you want the first middle node when there are two? → Adjust condition to return slow when fast.next.next is null.
• Can you do it recursively? → Yes, but iterative is preferred for space efficiency.

💡 These follow-ups test your flexibility and deeper understanding of pointer movement and recursion.

🔍

Pattern Recognition

When to Use

1) You need to find a middle or midpoint in a linked list. 2) The problem involves traversal without indexing. 3) The problem hints at two pointers moving at different speeds. 4) You want to optimize from multiple passes to a single pass.

Signature Phrases

middle node of linked listfast and slow pointerstwo pointers moving at different speeds

NOT This Pattern When

Problems that require sorting or random access arrays are different patterns.

Similar Problems

Palindrome Linked List - uses fast and slow pointers to find middleLinked List Cycle - uses fast and slow pointers to detect cycleRemove Nth Node From End of List - uses two pointers spaced apart

Practice

1. You are given a singly linked list and asked to reorder it so that the nodes are arranged in the order: first node, last node, second node, second last node, and so on. Which approach guarantees an optimal in-place solution with O(n) time and O(1) extra space?

easy

A. Use a brute force approach by storing all nodes in an array and then rearranging pointers.

B. Use dynamic programming to store intermediate reorder states and build the final list.

C. Recursively reorder the list by traversing to the end and merging nodes from both ends.

D. Find the middle of the list using fast and slow pointers, reverse the second half, then merge the two halves.

Solution

1. Step 1: Identify the problem constraints

   The problem requires reordering the list in-place with O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Brute force uses extra space, recursion uses O(n) stack space, and DP is not applicable here. The fast-slow pointer approach finds the middle, reverses the second half, and merges in-place efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Fast-slow pointer approach is classic for in-place reorder [OK]

Hint: Fast-slow pointer + reverse + merge is classic in-place reorder [OK]

Common Mistakes:

• Thinking recursion is O(1) space
• Using DP for linked list reorder
• Assuming array storage is in-place

2. What is the time complexity of the optimized fast-slow pointer algorithm for detecting a cycle in a circular array of length n, where each element can be positive or negative steps? Assume the algorithm marks visited elements in-place to avoid repeated work.

medium

A. O(n) because each element is visited at most twice due to in-place marking

B. O(n) average but O(n^2) worst-case if cycles overlap heavily

C. O(n log n) due to repeated modulo operations and pointer jumps

D. O(n^2) because each element can be visited multiple times during cycle checks

Solution

1. Step 1: Analyze outer and inner loops

   Each index is processed once in the outer loop; inner while loop visits elements until cycle or zero marking.

2. Step 2: Check effect of in-place marking

   Marking visited elements as zero prevents revisiting, ensuring total visits across all iterations is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   In-place marking guarantees linear time complexity [OK]

Hint: In-place marking -> each element visited once [OK]

Common Mistakes:

• Assuming repeated visits cause O(n²)
• Ignoring marking effect
• Confusing modulo cost as log factor

3. Consider the following code snippet for palindrome check. Which line contains a subtle bug that can cause incorrect results on odd-length lists?

medium

A. Line where second_half_start is assigned by reversing slow

B. Line where slow pointer is advanced in the while loop

C. Line where first_half_start and second_half_start values are compared

D. Line where fast pointer is advanced in the while loop

Solution

1. Step 1: Understand midpoint selection

   For odd-length lists, slow points to the middle node, which should be skipped before reversal.

2. Step 2: Identify bug in reversal start

   Reversing from slow includes the middle node, causing mismatch in comparison.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach skips middle node before reversal on odd-length lists [OK]

Hint: Check if middle node is excluded before reversing second half [OK]

Common Mistakes:

• Reversing from slow without skipping middle node
• Incorrect fast/slow pointer advancement
• Not handling odd-length lists separately

4. Suppose the Happy Number problem is extended to allow negative integers as input. Which modification to the optimal algorithm is necessary to correctly handle negative inputs?

hard

A. Add absolute value conversion before processing digits to handle negatives

B. Add negative numbers to the cycle set to detect cycles

C. Modify get_next to handle negative digits separately

D. No change needed; negative numbers will eventually reach 1 or cycle

Solution

1. Step 1: Understand digit extraction for negative numbers

   Digit extraction using modulo and division assumes non-negative numbers. Negative inputs cause incorrect digit processing.

2. Step 2: Convert input to absolute value before processing

   Taking absolute value ensures digits are correctly extracted and sum of squares computed properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Absolute value fixes digit extraction for negatives [OK]

Hint: Digit extraction requires non-negative numbers [OK]

Common Mistakes:

• Assuming negative inputs work without modification

5. If the linked list nodes can be reused multiple times (i.e., the list is cyclic or can be traversed repeatedly), which modification is necessary to the optimal palindrome check algorithm?

hard

A. No modification needed; the current algorithm works as is.

B. Use a stack to store first half values instead of reversing to avoid modifying the list.

C. Convert the list to an array to handle multiple traversals safely.

D. Restore the reversed second half to original order after comparison to preserve list structure.

Solution

1. Step 1: Understand reuse implications

   If nodes are reused or list is cyclic, modifying it breaks future traversals.

2. Step 2: Restore list after palindrome check

   Reversing second half in-place must be undone to preserve original list structure.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Restoring reversed half ensures list integrity for reuse [OK]

Hint: Always restore list after in-place reversal if list is reused [OK]

Common Mistakes:

• Ignoring list restoration causing side effects
• Switching to stack approach unnecessarily increasing space
• Assuming array conversion is always better