Find Middle of Linked List

Find the middle node of a linked list using the two-pointer technique

Language Selection

Choose your preferred programming language

Showing: Python

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.

Input/Output Specifications

Input: Head of a singly linked list
Output: Middle node of the linked list
Constraints:
- The number of nodes in the list is in the range [1, 100]
- 1 <= Node.val <= 100

Examples

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.

Solutions

Approach 1: Two Pointers (Slow and Fast)

This approach uses two pointers moving at different speeds. 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, the slow pointer will be at the middle.

Algorithm:

Initialize two pointers: slow and fast both pointing to head
Move slow one step and fast two steps at each iteration
Continue until fast reaches the end or fast.next is null
Return the slow pointer which points to the middle node

Python:

def middleNode(head):
    """
    Find middle node using slow and fast pointers
    Time: O(n)
    Space: O(1)
    """
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow

Java:

class Solution {
    /**
     * Find middle node using slow and fast pointers
     * Time: O(n)
     * Space: O(1)
     */
    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;
    }
}

Go:

// middleNode - Find middle node using slow and fast pointers
// Time: O(n)
// Space: O(1)
func middleNode(head *ListNode) *ListNode {
    slow := head
    fast := head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    return slow
}

JavaScript:

/**
 * Find middle node using slow and fast pointers
 * Time: O(n)
 * Space: O(1)
 */
function middleNode(head) {
    let slow = head;
    let fast = head;
    
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
}

C#:

public class Solution {
    /// <summary>
    /// Find middle node using slow and fast pointers
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    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;
    }
}

Approach 2: Count and Traverse

This approach first counts the total number of nodes, then traverses to the middle position.

Algorithm:

First pass: count the total number of nodes
Calculate the middle position: count / 2
Second pass: traverse to the middle position and return that node

Python:

def middleNodeCount(head):
    """
    Find middle node by counting nodes first
    Time: O(n)
    Space: O(1)
    """
    # Count total nodes
    count = 0
    current = head
    while current:
        count += 1
        current = current.next
    
    # Find middle position
    middle_pos = count // 2
    
    # Traverse to middle
    current = head
    for _ in range(middle_pos):
        current = current.next
    
    return current

Java:

class Solution {
    /**
     * Find middle node by counting nodes first
     * Time: O(n)
     * Space: O(1)
     */
    public ListNode middleNodeCount(ListNode head) {
        // Count total nodes
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        
        // Find middle position
        int middlePos = count / 2;
        
        // Traverse to middle
        current = head;
        for (int i = 0; i < middlePos; i++) {
            current = current.next;
        }
        
        return current;
    }
}

Go:

// middleNodeCount - Find middle node by counting nodes first
// Time: O(n)
// Space: O(1)
func middleNodeCount(head *ListNode) *ListNode {
    // Count total nodes
    count := 0
    current := head
    for current != nil {
        count++
        current = current.Next
    }
    
    // Find middle position
    middlePos := count / 2
    
    // Traverse to middle
    current = head
    for i := 0; i < middlePos; i++ {
        current = current.Next
    }
    
    return current
}

JavaScript:

/**
 * Find middle node by counting nodes first
 * Time: O(n)
 * Space: O(1)
 */
function middleNodeCount(head) {
    // Count total nodes
    let count = 0;
    let current = head;
    while (current !== null) {
        count++;
        current = current.next;
    }
    
    // Find middle position
    const middlePos = Math.floor(count / 2);
    
    // Traverse to middle
    current = head;
    for (let i = 0; i < middlePos; i++) {
        current = current.next;
    }
    
    return current;
}

C#:

public class Solution {
    /// <summary>
    /// Find middle node by counting nodes first
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public ListNode MiddleNodeCount(ListNode head) {
        // Count total nodes
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        
        // Find middle position
        int middlePos = count / 2;
        
        // Traverse to middle
        current = head;
        for (int i = 0; i < middlePos; i++) {
            current = current.next;
        }
        
        return current;
    }
}

Key Insights

Tortoise and Hare: The two-pointer technique is optimal for finding the middle
Single pass: Two-pointer approach finds the middle in one traversal
Even length handling: When there are two middle nodes, we return the second one
Pointer synchronization: Fast pointer moves twice as fast as slow pointer
Termination condition: Stop when fast reaches end or fast.next is null

Edge Cases

Single node list (return the only node)
Two node list (return the second node)
Odd length list (return the true middle)
Even length list (return the second middle)
Very long lists (performance consideration)

Test Cases

# Test case 1: Odd length list
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
head1.next.next.next.next = ListNode(5)
# Expected: Node with value 3

# Test case 2: Even length list
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
head2.next.next.next = ListNode(4)
head2.next.next.next.next = ListNode(5)
head2.next.next.next.next.next = ListNode(6)
# Expected: Node with value 4

# Test case 3: Single node
head3 = ListNode(1)
# Expected: Node with value 1

# Test case 4: Two nodes
head4 = ListNode(1)
head4.next = ListNode(2)
# Expected: Node with value 2

Follow-up Questions

How would you find the first middle node in an even-length list?
Can you find the middle node without using extra space?
How would you find the kth node from the end?
What if you need to find multiple middle nodes?

Common Mistakes

Not handling the even-length case correctly
Incorrect termination condition for the fast pointer
Off-by-one errors in pointer movement
Not considering single node lists
Infinite loops when pointers aren’t moved correctly
Returning the wrong node for even-length lists