# Middle of the Linked List
**Difficulty:** EASY
[External](https://leetcode.com/problems/middle-of-the-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/middle-of-the-linked-list
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Linked List
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Zoho](https://scaleengineer.com/companies/zoho), [Bosch](https://scaleengineer.com/companies/bosch)
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/middle-of-the-linked-list/image0.jpg) 

**Input:** head = [1,2,3,4,5]
**Output:** [3,4,5]
**Explanation:** The middle node of the list is node 3.

**Example 2:**

![](https://assets.glich.co/dsa/middle-of-the-linked-list/image1.jpg) 

**Input:** head = [1,2,3,4,5,6]
**Output:** [4,5,6]
**Explanation:** Since the list has two middle nodes with values 3 and 4, we return the second one.

**Constraints:**

* The number of nodes in the list is in the range `[1, 100]`.
* `1 <= Node.val <= 100`

# Approaches
## Store Nodes in an Array
This approach involves converting the linked list into an array. We traverse the linked list from the beginning to the end and store each node in a dynamic array. Once all nodes are stored, the middle node can be found by accessing the element at the middle index of the array, which is `array.size() / 2`.
**Time:** O(N), where N is the number of nodes in the linked list. We need to traverse the entire list once to populate the array. · **Space:** O(N), as we need to store all N nodes in the `ArrayList`.
**Pros:** Simple to understand and implement.; Provides random access to any node once the array is built.
**Cons:** High space complexity, which can be a problem for very large linked lists.; Less efficient than other approaches that use constant space.
### Explanation
The core idea is to leverage the random-access capability of an array. A linked list does not allow direct access to an element by its index, so we first transform it into a data structure that does.

We initialize an `ArrayList` of `ListNode`. Then, we iterate through the linked list with a pointer, starting from the `head`. In each iteration, we add the current node to our `ArrayList` and move the pointer to the next node. This continues until we reach the end of the list (i.e., the pointer becomes `null`).

After the loop, our `ArrayList` contains all the nodes of the linked list in order. The size of the list, `N`, is simply `list.size()`. The problem asks for the middle node, which for a list of size `N` is the node at index `N / 2`. We can directly retrieve this node from our `ArrayList` and return it.

For example, if the list is `[1,2,3,4,5]`, `N=5`. The middle index is `5/2 = 2`. The node at index 2 is `3`.
If the list is `[1,2,3,4,5,6]`, `N=6`. The middle index is `6/2 = 3`. The node at index 3 is `4`, which is the second middle node as required.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        java.util.List<ListNode> nodes = new java.util.ArrayList<>();
        ListNode current = head;
        while (current != null) {
            nodes.add(current);
            current = current.next;
        }
        int middleIndex = nodes.size() / 2;
        return nodes.get(middleIndex);
    }
}
```
### Algorithm
*   1. Create an `ArrayList` to store the `ListNode` objects.
*   2. Initialize a pointer `current` to the `head` of the linked list.
*   3. Traverse the linked list using the `current` pointer. In each step:
    *   Add the `current` node to the `ArrayList`.
    *   Move `current` to the next node (`current = current.next`).
*   4. After the traversal is complete, calculate the middle index as `middleIndex = list.size() / 2`.
*   5. Return the node at `middleIndex` from the `ArrayList`.

## Two-Pass Traversal
This approach avoids using extra space by traversing the list twice. The first pass is to count the total number of nodes. The second pass is to traverse the list again from the head to the middle node and return it.
**Time:** O(N), where N is the number of nodes. The list is traversed 1.5 times in the worst case (once to count, and N/2 times to find the middle), which simplifies to O(N). · **Space:** O(1), as we only use a few variables (`count`, `current`, `middleSteps`) regardless of the list size.
**Pros:** Space efficient, using only constant extra space.; Conceptually straightforward.
**Cons:** Requires two passes over the linked list, which is less efficient than a single-pass solution.
### Explanation
This method is a space-optimized improvement over the array-based approach. Instead of storing all nodes, we first determine the length of the list and then find the middle node based on that length.

The algorithm proceeds in two main steps:
1.  **First Pass (Count Nodes):** We initialize a counter to zero and a pointer to the `head`. We traverse the entire list, incrementing the counter for each node until we reach the end. Let the final count be `N`.
2.  **Second Pass (Find Middle Node):** We calculate the position of the middle node, which is `N / 2`. We reset our pointer back to the `head`. Then, we traverse the list again, this time for `N / 2` steps. The node at which the pointer stops is the middle node.

For a list `[1,2,3,4,5]`, `N=5`. The middle position is `5/2 = 2`. We traverse 2 steps from the head: `1 -> 2 -> 3`. The result is node `3`.
For a list `[1,2,3,4,5,6]`, `N=6`. The middle position is `6/2 = 3`. We traverse 3 steps from the head: `1 -> 2 -> 3 -> 4`. The result is node `4`.

This approach correctly identifies the second middle node in case of an even-length list.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        // First pass: count the number of nodes
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        
        // Calculate the middle index
        int middleIndex = count / 2;
        
        // Second pass: traverse to the middle node
        current = head;
        for (int i = 0; i < middleIndex; i++) {
            current = current.next;
        }
        
        return current;
    }
}
```
### Algorithm
*   1. Initialize a counter `count` to 0 and a pointer `current` to `head`.
*   2. Traverse the list with `current` to its end, incrementing `count` for each node.
*   3. After the first pass, `count` will hold the total number of nodes.
*   4. Calculate the number of steps to reach the middle node: `middleSteps = count / 2`.
*   5. Reset the `current` pointer back to `head`.
*   6. Traverse the list again from the `head` for `middleSteps` times.
*   7. Return the `current` node.

## Fast and Slow Pointer (Tortoise and Hare Algorithm)
This is the most optimal approach, solving the problem in a single pass with constant space. It uses two pointers, a `slow` pointer and a `fast` pointer. The `slow` pointer moves one step at a time, while the `fast` pointer moves two steps at a time. When the `fast` pointer reaches the end of the list, the `slow` pointer will be at the middle.
**Time:** O(N), where N is the number of nodes. Although it's O(N), it's more efficient than the two-pass approach as it only traverses the list once. The `slow` pointer makes N/2 moves. · **Space:** O(1), as it only uses two extra pointers, regardless of the list's size.
**Pros:** Most efficient solution in terms of both time (single pass) and space (constant).; Elegant and a common pattern for solving linked list problems.
**Cons:** The logic might be slightly less intuitive for beginners compared to the counting approach.
### Explanation
This classic algorithm, often called the 'Tortoise and Hare' algorithm, is highly efficient for finding the middle of a linked list. The intuition is that by the time the fast pointer (hare) reaches the end of the race (the end of the list), the slow pointer (tortoise) will have covered exactly half the distance and will be at the midpoint.

We initialize both `slow` and `fast` pointers to the `head` of the list. Then, we enter a loop that continues as long as `fast` and `fast.next` are not `null`. Inside the loop, we advance `slow` by one node (`slow = slow.next`) and `fast` by two nodes (`fast = fast.next.next`).

Let's trace this for both odd and even length lists:
*   **Odd length (e.g., `[1,2,3,4,5]`)**:
    *   Initial: `slow` at 1, `fast` at 1.
    *   Step 1: `slow` at 2, `fast` at 3.
    *   Step 2: `slow` at 3, `fast` at 5.
    *   Now, `fast.next` is `null`. The loop terminates. `slow` is at node `3`, which is the middle.
*   **Even length (e.g., `[1,2,3,4,5,6]`)**:
    *   Initial: `slow` at 1, `fast` at 1.
    *   Step 1: `slow` at 2, `fast` at 3.
    *   Step 2: `slow` at 3, `fast` at 5.
    *   Step 3: `slow` at 4, `fast` becomes `null` (since `fast.next` was 6, `fast.next.next` is `null`).
    *   The loop terminates. `slow` is at node `4`, which is the second middle node, as required.

This single-pass approach is both time and space efficient.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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;
    }
}
```
### Algorithm
*   1. Initialize two pointers, `slow` and `fast`, both pointing to the `head` of the list.
*   2. Start a loop that continues as long as `fast` is not `null` and `fast.next` is not `null`.
*   3. Inside the loop:
    *   Move `slow` one step forward: `slow = slow.next`.
    *   Move `fast` two steps forward: `fast = fast.next.next`.
*   4. When the loop terminates, the `slow` pointer will be at the middle node of the linked list.
*   5. Return the `slow` pointer.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { 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 ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ 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 ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def middleNode ( self , head : ListNode ) -> ListNode : slow = fast = head while fast and fast . next : slow , fast = slow . next , fast . next . next return slow
```