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 an array of n + 1 integers where each integer is between 1 and n (inclusive). There is exactly one duplicate number but it could be repeated multiple times. Which approach guarantees finding the duplicate in O(n) time and O(1) space without modifying the input array?

easy

A. Sort the array and then scan for consecutive duplicates

B. Use two pointers moving at different speeds to detect a cycle in the array values

C. Use a hash set to track seen numbers and return the first duplicate

D. Use nested loops to compare every pair of elements

Solution

1. Step 1: Understand the problem constraints

   The array contains n+1 integers with values from 1 to n, guaranteeing at least one duplicate. The input cannot be modified and extra space must be O(1).

2. Step 2: Identify the approach that fits constraints

   Sorting modifies the array, hash sets use extra space, nested loops are O(n²). Floyd's cycle detection uses two pointers at different speeds to find a cycle in O(n) time and O(1) space without modifying the array.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer cycle detection fits all constraints [OK]

Hint: Cycle detection fits O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming sorting is allowed despite input constraints
• Believing hash sets use constant space
• Thinking nested loops are efficient enough

2. You are given a singly linked list and need to determine the length of a cycle if one exists. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use dynamic programming to store cycle lengths for sublists and combine results.

B. Use a hash set to store visited nodes and count cycle length upon revisiting a node.

C. Use two pointers moving at different speeds to detect the cycle and then count its length by traversing the cycle once.

D. Use a recursive depth-first search to detect cycles and count their lengths.

Solution

1. Step 1: Understand the problem constraints

   The problem requires detecting a cycle and counting its length efficiently in a linked list.

2. Step 2: Evaluate approaches for time and space complexity

   Using two pointers (fast and slow) allows cycle detection in O(n) time and O(1) space, then counting the cycle length by traversing the cycle once is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Fast-slow pointer approach is classic for cycle detection with constant space [OK]

Hint: Fast-slow pointers detect cycles in O(1) space [OK]

Common Mistakes:

• Believing hash sets are optimal due to extra space
• Confusing DP with cycle detection
• Using recursion unnecessarily

3. What is the time complexity of the optimized iterative approach for deleting N nodes after skipping M nodes in a singly linked list of length n? Assume M and N are constants.

medium

A. O(n)

B. O(n * (M + N))

C. O(n^2)

D. O(n + M + N)

Solution

1. Step 1: Identify loop behavior

   The algorithm traverses the list once, moving forward by skipping M nodes and deleting N nodes repeatedly.

2. Step 2: Analyze complexity

   Since M and N are constants, each iteration moves forward by at least M+N nodes, so total steps proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass traversal yields O(n) time complexity [OK]

Hint: Constant M, N means linear traversal dominates [OK]

Common Mistakes:

• Mistaking nested loops causing O(n*(M+N))
• Assuming quadratic due to inner loops
• Ignoring that M and N are constants

4. Examine the following buggy code for cycle detection using fast and slow pointers. Which line contains the subtle bug that can cause incorrect cycle detection or runtime error?

medium

A. Line 3: while fast and fast.next:

B. Line 5: slow = slow.next

C. Line 6: fast = fast.next.next

D. Line 4: if slow == fast:

Solution

1. Step 1: Understand pointer initialization and loop

   Both slow and fast start at head. The loop checks fast and fast.next to avoid null dereference.

2. Step 2: Identify when pointers are compared

   Comparing slow == fast before moving pointers causes immediate true at start (both at head), falsely detecting a cycle. Moving pointers first then comparing avoids this.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Comparison must happen after moving pointers to avoid false positive [OK]

Hint: Check pointers after moving, not before, to avoid false positives [OK]

Common Mistakes:

• Comparing pointers before moving them
• Not checking fast.next before advancing fast

5. If the linked list nodes cannot be modified (no extra fields allowed) and you want to detect a cycle in O(1) space, which approach correctly adapts Floyd's cycle detection algorithm to also find the entry point of the cycle?

hard

A. Use a hash set to store nodes and find the first repeated node as the cycle start.

B. Modify node values temporarily to mark visited nodes and revert after detection.

C. After detecting the cycle, reset slow to head and move both pointers one step at a time until they meet; the meeting point is the cycle start.

D. Run the fast pointer twice as fast until it reaches the end, then backtrack to find the cycle start.

Solution

1. Step 1: Detect cycle using fast and slow pointers

   When fast and slow meet, a cycle exists but the meeting point is not necessarily the cycle start.

2. Step 2: Find cycle entry point

   Reset slow to head, then move slow and fast one step at a time; their meeting point is the cycle start node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Standard Floyd's algorithm extension for cycle entry detection [OK]

Hint: Reset slow to head after detection to find cycle start [OK]

Common Mistakes:

• Using extra memory when O(1) space required
• Modifying node values disallowed
• Incorrect pointer movement after detection