Middle of the Linked List

class Solution {
public:
    ListNode* findMiddle(ListNode* start) {
        ListNode* turtle = start;
        ListNode* rabbit = start;
        while (rabbit != NULL && rabbit->next != NULL) {
            turtle = turtle->next;
            rabbit = rabbit->next->next;
        }
        return turtle;
    }
};

This solution focuses on finding the middle node of a singly linked list in C++. The implemented method, findMiddle, takes a single argument, start, which is a pointer to the head node of the list. The algorithm employs the two-pointer technique where:

• turtle moves one step at a time
• rabbit moves two steps at a time

By the time rabbit reaches the end of the list or becomes NULL, turtle is exactly halfway through the list. Consequently, turtle represents the middle node of the list at this point. The function will return turtle as the result, providing the pointer to the middle node of the linked list. This approach ensures an efficient traversal with a time complexity of O(n/2), where n is the total number of nodes in the linked list.

class Solution {
    public ListNode findMiddle(ListNode start) {
        ListNode slowPtr = start, fastPtr = start;
        while (fastPtr != null && fastPtr.next != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }
        return slowPtr;
    }
}

This Java program provides a method to find the middle node of a singly linked list using the two-pointer technique, commonly known as the slow and fast pointer approach. The class Solution has one method named findMiddle that accepts the head of the linked list as its parameter start.

Follow these steps to find the middle of the linked list:

1. Initialize two pointers, slowPtr and fastPtr, at the head of the linked list.
2. Traverse the list using a loop. Move slowPtr one step at a time and fastPtr two steps at a time.
3. Continue the loop until fastPtr or fastPtr.next becomes null.
4. When fastPtr reaches the end of the list, slowPtr will be positioned at the middle node.

By the completion of the loop, slowPtr will point to the middle node of the linked list, which is then returned.

This method effectively finds the middle element with a time complexity of O(n) and a space complexity of O(1), making it efficient for use in various linked list problems, especially where quick access to the middle element is required.

var findMiddle = function(start) {
    let slowPtr = fastPtr = start;
    while (fastPtr && fastPtr.next) {
        slowPtr = slowPtr.next;
        fastPtr = fastPtr.next.next;
    }
    return slowPtr;
};

The given JavaScript function, findMiddle, efficiently locates the middle node of a singly linked list using the two-pointer technique. This approach utilizes two pointers, slowPtr and fastPtr, both starting at the head of the list. As you traverse the list:

• slowPtr advances one node at a time.
• fastPtr advances two nodes at a time.

This difference in speed ensures that when fastPtr reaches the end of the list or the last node (in the case of an even number of nodes), slowPtr will be at the middle node. This method is optimal as it only requires a single pass through the list, achieving a time complexity of O(n) and a space complexity of O(1), making it both time and space efficient. The function returns slowPtr, which at the termination of the loop, points to the middle node of the list.

class Solution:
    def findMiddle(self, start):
        slow_ptr = fast_ptr = start
        while fast_ptr and fast_ptr.next:
            slow_ptr = slow_ptr.next
            fast_ptr = fast_ptr.next.next
        return slow_ptr

This solution finds the middle node of a singly linked list using the Python programming language. The approach involves two pointers, slow_ptr and fast_ptr. Both pointers begin at the start of the list. The fast_ptr moves at twice the speed of the slow_ptr. This means for every node that slow_ptr advances, fast_ptr moves two nodes ahead. The loop continues until fast_ptr reaches the end of the list or the node before the last if the length is even. At the termination of the loop, slow_ptr will be pointing to the middle node of the list, which is then returned by the function findMiddle.

• Key features of the approach:
  • Utilizes two-pointer technique for optimal efficiency.
  • Achieves a time complexity of O(n) and a space complexity of O(1), making it efficient in terms of both time and space.

Ensure to have a linked list node class defined with at least the attributes next and possibly val for this function to operate correctly. To find the middle of the linked list using this implementation:

1. Create an instance of a linked list and populate it with nodes.
2. Create an instance of the Solution class.
3. Call the findMiddle method with the head of the list as the argument.