Scale Engineer

Middle of the Linked List

Easy
#0830Time: 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.5 companies
Patterns
Two Pointers
Data structures
Linked List
Companies
IntuitQualcommWalmart LabsZoho

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

/** * 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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem