1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11class Solution {
12    /**
13     * Finds the middle node of a linked list.
14     * If the list has an even number of nodes, returns the second middle node.
15     * Uses the two-pointer technique (slow and fast pointers).
16     * 
17     * @param head The head of the linked list
18     * @return The middle node of the linked list
19     */
20    public ListNode middleNode(ListNode head) {
21        // Initialize two pointers at the head of the list
22        // slowPointer moves one step at a time
23        // fastPointer moves two steps at a time
24        ListNode slowPointer = head;
25        ListNode fastPointer = head;
26      
27        // Traverse the list until fastPointer reaches the end
28        // When fastPointer reaches the end, slowPointer will be at the middle
29        while (fastPointer != null && fastPointer.next != null) {
30            // Move slowPointer one step forward
31            slowPointer = slowPointer.next;
32            // Move fastPointer two steps forward
33            fastPointer = fastPointer.next.next;
34        }
35      
36        // Return the middle node (where slowPointer is positioned)
37        return slowPointer;
38    }
39}
40

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    /**
14     * Find the middle node of a linked list.
15     * Uses the two-pointer technique (slow and fast pointers).
16     * 
17     * @param head The head of the linked list
18     * @return The middle node of the linked list
19     *         If the list has an even number of nodes, returns the second middle node
20     */
21    ListNode* middleNode(ListNode* head) {
22        // Initialize two pointers at the head of the list
23        ListNode* slowPointer = head;
24        ListNode* fastPointer = head;
25      
26        // Move fast pointer twice as fast as slow pointer
27        // When fast pointer reaches the end, slow pointer will be at the middle
28        while (fastPointer != nullptr && fastPointer->next != nullptr) {
29            // Move slow pointer one step forward
30            slowPointer = slowPointer->next;
31          
32            // Move fast pointer two steps forward
33            fastPointer = fastPointer->next->next;
34        }
35      
36        // Return the middle node (pointed by slow pointer)
37        return slowPointer;
38    }
39};
40

1/**
2 * Definition for singly-linked list node
3 */
4interface ListNode {
5    val: number;
6    next: ListNode | null;
7}
8
9/**
10 * Finds the middle node of a linked list using the two-pointer technique
11 * 
12 * @param head - The head node of the linked list
13 * @returns The middle node of the linked list, or the second middle node if the list has an even number of nodes
14 * 
15 * Time Complexity: O(n) where n is the number of nodes in the linked list
16 * Space Complexity: O(1) as we only use two pointers
17 * 
18 * Algorithm:
19 * - Uses fast and slow pointers (Floyd's Tortoise and Hare algorithm)
20 * - Fast pointer moves two steps at a time
21 * - Slow pointer moves one step at a time
22 * - When fast pointer reaches the end, slow pointer will be at the middle
23 */
24function middleNode(head: ListNode | null): ListNode | null {
25    // Initialize both pointers at the head of the list
26    let fastPointer: ListNode | null = head;
27    let slowPointer: ListNode | null = head;
28  
29    // Traverse the list until fast pointer reaches the end
30    // Check both fast pointer and its next node to avoid null reference
31    while (fastPointer !== null && fastPointer.next !== null) {
32        // Move fast pointer two steps forward
33        fastPointer = fastPointer.next.next;
34        // Move slow pointer one step forward
35        slowPointer = slowPointer.next!;
36    }
37  
38    // Return the slow pointer which is now at the middle node
39    return slowPointer;
40}
41