Middle of the Linked List: 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 the nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

Try this Problem on your own or check similar problems:

1. Delete the Middle Node of a Linked List
2. Maximum Twin Sum of a Linked List

Solution:

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

This is a simple problem easily solved with fast and slow pointers. We have two pointers slow (moving one step at the time) and fast (moving two steps at the time). After fast has reached the end of the linked list, the slow one would only have covered half (actually list.length / 2 would be “index” in the list slow is pointing when fast reached the end which is exactly the middle element). We traverse the list only once leading to linear time complexity.