Find the middle of a given linked list

The Tortoise and Hare Algorithm is a popular algorithm used to find the median of a linked list. It derives its name from the fable of the tortoise and the hare, where the tortoise wins due to its steady pace. This algorithm provides an efficient way to locate the middle element of a linked list.

Here’s how the algorithm works:

1. Start with two pointers: one that moves one step at a time (slow pointer) and another that moves two steps at a time (fast pointer).

2. While the fast pointer is not null and its next pointer is also not null, continue iterating through the linked list.

3. In each iteration, move the slow pointer one step forward and the fast pointer two steps forward.

4. When the fast pointer reaches the end of the linked list (i.e., it becomes null or its next pointer becomes null), the slow pointer will be at the middle of the list.

5. If the length of the linked list is even, the slow pointer will be at the second middle element.

6. If the length of the linked list is odd, the slow pointer will be at the exact middle element.

The time complexity of this algorithm is O(n), where n is the number of elements in the linked list. The space complexity is O(1), as no additional data structures are used apart from the two pointers.

Here’s an example implementation of the algorithm in JavaScript:

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    push(value) {
        const newNode = new Node(value);
        if (this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }

    findMid() {
        let slow = this.head;
        let fast = this.head;
        while (fast !== null && fast.next !== null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

const list = new LinkedList();
list.push(1);
list.push(2);
list.push(3);
list.push(4);
list.push(5);
list.push(6);
list.push(7);

console.log(list.findMid().value);

In the above example, we create a linked list and push elements into it. Then, we call the findMid() method, which returns the middle node of the linked list. Finally, we print the value of the middle node using console.log().

This algorithm provides an efficient way to find the middle element of a linked list in a single pass, making it useful in various scenarios where the median or middle value is required.