Middle Element in Linked List

Solution

Basic idea

To find the middle element of a linked list, we can use the two-pointer technique. We can have two pointers, slow and fast, starting from the head of the linked list. 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 element.

const findMiddleElement = (head) => {
    if (!head) {
        return null; // Empty list
    }
    
    let slow = head;
    let fast = head;
    
    // Move fast pointer two steps ahead and slow pointer one step ahead
    // When fast pointer reaches the end, slow pointer will be at the middle
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow.value;
}

Algorithm Detailed Explanation

1. Initialize two pointers, slow and fast, pointing to the head of the linked list.
2. Traverse the linked list using the two-pointer technique:
   • Move the slow pointer one step ahead.
   • Move the fast pointer two steps ahead.
3. When the fast pointer reaches the end of the list (i.e., fast or fast.next is null), the slow pointer will be at the middle element.
4. Return the value of the middle element.

Complexity Analysis

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. The space complexity is O(1) since we are using only two pointers.