[Solved]  Middle of the Linked List – 876 C++, Java, Python – Microsoft, Google , Amazon, Media.net

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

Solution

1-Intuition
The problem requires finding the middle node of a given singly-linked list. One approach to solving this problem is to iterate through the list to determine its length. Then, we can traverse halfway through the list to find the middle node.

Approach
Create a function to calculate the length of the linked list.
Calculate the length of the list.
Traverse halfway through the list to find the middle node.
Return the middle node.

Complexity
Time complexity:

Calculating the length of the linked list takes O(n) time.
Traversing halfway through the list also takes O(n/2) time.
Overall time complexity is O(n).
Space complexity:

The space complexity is O(1) because we are not using any extra space proportional to the size of the input.

2 – Initialization: Start with two pointers, fast and slow, both pointing to the head of the list.

Traversal: Move the fast pointer two steps at a time and the slow pointer one step at a time. This ensures that when the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

Find the Middle Node: After traversal, the slow pointer will be at the middle node of the list.

Edge Case Handling: Check if the list is empty or contains only one node. In such cases, the middle node is the head itself.

Return: Return the node pointed to by the slow pointer as the middle node.

Time complexity: O(n)

Space complexity: O(1)

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
        
    }
}

class Solution(object):
    def middleNode(self, head):
        slow_pointer = head
        fast_pointer = head

        while fast_pointer is not None and fast_pointer.next is not None:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next

        return slow_pointer

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slowPointer = head;
        ListNode* fastPointer = head;

        while (fastPointer != nullptr && fastPointer->next != nullptr) {
            slowPointer = slowPointer->next;
            fastPointer = fastPointer->next->next;
        }

        return slowPointer;
    }
};