Let’s understand the problem!

Write a programme that discover the middle node of a singly linked list given a single node. If the number of nodes is even, we must return the second middle node. 

Examples 

Input: 5->4->3->2->1, Output: 3

Explanation: Because there are five nodes in this diagram, there is one centre node, which is 3. 

Input: 6->5->4->3->2->1, Output: 3

Explanation: There are six nodes, with the first middle node being four and the second middle node being three. As a result, we must return the pointer to node value 3.

Approaches to solving the problem were discussed

• Using more RAM, a brute force strategy is used. 
• Double traversal of the linked list by counting nodes 
• Counting nodes: traversal of the linked list in a single step 
• Using slow and fast pointers, an effective solution was found.

A brute force approach  using extra memory

The main idea is to keep each linked list node (in the same order) in an extra array with a size equal to the linked list’s length, and then access the middle node by accessing the array’s middle index.

Solution Pseudocode

ListNode getMiddleNode(ListNode head) 

{

    int length = listLength(head)

    ListNode temp[length]

    int count = 0

    while (head->next != null) 

    {

        temp[count] = head

        count = count + 1

        head = head->next

    }

    return temp[count/2]

}

Analysis of time and spatial complexity 

Suppose the length of the linked list is n. So the time complexity = Time complexity of finding the length of linked list + Time complexity of storing nodes into extra memory = O(n) + O(n) = O(n)

For storing nodes in an n-size array, the space complexity is O(n).

Double traversal of the linked list by counting nodes 

Solution Idea

We’re using additional space to discover the centre node of the linked list in the way above. The key challenge now is if we can reduce space complexity to O(1). 

One possibility is to count the number of nodes in the linked list before traversing it count/2 times. So we’ll be at the middle node at the conclusion of the second traverse.

Steps to a Solution 

• The variable count is set to 0 by default. 
• We also create a list pointer middle to keep track of the middle node, which is set to head. 
• Now we count the number of nodes in a loop till head!= NULL. 
• Now we run another loop till I n/2 and increment the middle pointer value in each iteration. 
• We return the middle pointer at the end of the second loop.

Solution Pseudocode

ListNode getMiddleNode(ListNode head)

{ 

    int count = 0

    ListNode middle = head

    while (head != NULL) 

    { 

        count = count + 1

        head = head->next

    }

    int i = 0

    while (i < count/2)

    { 

        middle = middle->next

        i = i + 1

    }

    return middle

}

Time and space complexity analysis

Suppose the length of the linked list is n. So the time complexity = Time complexity of finding the node count + Time complexity of finding the middle node = O(n) + O(n) = O(n)

Space complexity = O(1), as we are using constant extra space.

Counting nodes: traversal of the linked list in a single step 

Another idea: in a single traversal, we can track both the number of nodes and the middle node. 

• To keep track of the number of nodes, we create a variable count. 
• We also create a pointer middle to keep track of the middle node. 
• We’ll now run a loop until head!= NULL. 
• The count value is increased by one at each repetition. We increase the centre pointer by one when the count value is even. 
• The middle pointer will be at the middle node by the end of the loop, and we will return this value.

Solution Pseudocode

ListNode getMiddleNode(ListNode head)

{ 

    int count = 0

    ListNode middle = head

    while (head != NULL) 

    { 

        if (count % 2 == 0) 

            middle = middle->next

        count = count + 1

        head = head->next

    }

    return middle

}

Time and space complexity analysis

Every iteration, we run a single loop that does the same activities. Thus, time complexity equals O. (n). Because we are using constant extra space, the space complexity is O(1).