Middle of the Linked List

Problem 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.

Brute Force Solution

A straightforward approach involves iterating through the linked list twice. The first pass determines the length of the list. The second pass advances to the middle node.

Algorithm

1. Traverse the linked list to find the total number of nodes (count).
2. Calculate the middle index: middle = count / 2. If count is even, this gives the index of the second middle node.
3. Traverse the list again from the head, advancing middle times to reach the middle node.
4. Return the middle node.

Code (Java)

class Solution {
    public ListNode middleNode(ListNode head) {
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }

        int middle = count / 2;
        current = head;
        for (int i = 0; i < middle; i++) {
            current = current.next;
        }
        return current;
    }
}

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the linked list. We iterate through the list twice.
• Space Complexity: O(1), as we only use a few constant extra variables.

Optimal Solution: Tortoise and Hare (Two Pointer Approach)

This approach uses two pointers, often called "slow" and "fast" pointers. 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 node.

Algorithm

1. Initialize two pointers, slow and fast, both pointing to the head of the linked list.
2. While the fast pointer and fast.next are not null, advance slow by one step and fast by two steps.
3. When the loop terminates (i.e., fast reaches the end), slow will be pointing to the middle node.
4. Return the slow pointer.

Code (Java)

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 in the linked list. Although there are two pointers, we only traverse the list once.
• Space Complexity: O(1), as we only use two extra pointers.

Edge Cases

• Empty List: The problem states that the number of nodes is between 1 and 100, so this case won't occur.
• Single Node List: The slow and fast pointers will both start at the head. The while loop will immediately terminate because fast.next will be null. The slow pointer will be returned, which is the head.
• Even Length List: When the list has an even number of nodes, the fast pointer will reach the end (null) before the slow pointer. The slow pointer will be positioned at the second middle node, which is the expected behavior per the prompt.