Middle of a Linked List

Given the head of a linked list, the task is to find the middle. For example, the middle of 1-> 2->3->4->5 is 3. If there are two middle nodes (even count), return the second middle. For example, middle of 1->2->3->4->5->6 is 4.

Examples:

Input: Linked list: 1->2->3->4->5
Output: 3

Explanation: The given linked list is 1->2->3->4->5 and its middle is 3.

Input: Linked list: 2->4->6->7->5->1
Output: 7 

Explanation: The given linked list is 2->4->6->7->5->1 and its middle is 7.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 <= no. of nodes <= 10⁵

Approach 01:

class Solution {
public:
    // Function to find the middle of the linked list
    // Should return the data of the middle node. If the linked list is empty, return -1.
    int getMiddle(Node* head) {
        if (head == nullptr) {
            return -1; // If the linked list is empty, return -1
        }

        // First pass: Count the total number of nodes
        Node* currentNode = head;
        int totalNodes = 0;

        while (currentNode != nullptr) {
            totalNodes++;
            currentNode = currentNode->next;
        }

        // If the linked list has only one node, return its data
        if (totalNodes == 1) {
            return head->data;
        }

        // Calculate the position of the middle node
        int midPosition = totalNodes / 2;

        // Second pass: Traverse to the middle node
        currentNode = head;
        while (currentNode != nullptr) {
            if (midPosition == 0) {
                return currentNode->data;
            }
            currentNode = currentNode->next;
            midPosition--;
        }

        return -1; // Return -1 if something goes wrong
    }
};

class Solution:
    # Should return data of the middle node. If linked list is empty, then return -1
    def findMid(self, head):
        if not head:
            return -1

        # First pass: Count the total number of nodes
        currentNode = head
        totalNodes = 0
        
        while currentNode is not None:
            totalNodes += 1
            currentNode = currentNode.next

        # If the linked list has only one node, return its data
        if totalNodes == 1:
            return head.data

        # Calculate the position of the middle node
        if totalNodes % 2 == 0:
            midPosition = totalNodes // 2
        else:
            midPosition = totalNodes // 2

        # Second pass: Traverse to the middle node
        currentNode = head
        while currentNode is not None:
            if midPosition == 0:
                return currentNode.data
            currentNode = currentNode.next
            midPosition -= 1

        return -1  # Return -1 if something goes wrong

Time Complexity

• First Pass (Counting Total Nodes):

  The first pass through the linked list counts the total number of nodes. This operation takes \(O(n)\) time, where n is the number of nodes in the linked list.

• Second Pass (Finding the Middle Node):

  In the second pass, the algorithm traverses up to the middle node. This operation also takes \(O(n)\) time in the worst case, where the traversal goes up to half of the nodes.

• Overall Time Complexity:

  The overall time complexity is \(O(n) + O(n) = O(n)\).

Space Complexity

• Space for Variables:

  The solution uses a few local variables: currentNode for traversal, totalNodes to count the number of nodes, and midPosition to determine the middle node position. These require \(O(1)\) space.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\) because no additional data structures or dynamic memory allocations are used.