Middle of the Linked List

EASY

Description

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:

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

Example 2:

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

Checkout 3 different approaches to solve Middle of the Linked List. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

1. Initialize two pointers, slow and fast, both pointing to the head of the list.
1. Start a loop that continues as long as fast is not null and fast.next is not null.
1. Inside the loop:
- Move slow one step forward: slow = slow.next.
- Move fast two steps forward: fast = fast.next.next.
1. When the loop terminates, the slow pointer will be at the middle node of the linked list.
1. Return the slow pointer.

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.

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

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as it only uses two extra pointers, regardless of the list's size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Middle of the Linked List. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Middle of the Linked List

Patterns:

Two Pointers

Data Structures:

Linked List

Companies:

Intuit |Qualcomm |Walmart Labs |Zoho |