Beats 100%🔥🔥 | 2 Easy ans Simple C++ Approaches | Two Pointers ✅ |  | Detailed Explanation⭐️⭐️
Understanding the Problem:\n- You have a singly linked list where each node points to the next node.\n- You need to find the middle node of the linked list. If 
# Understanding the Problem:\n- You have a singly linked list where each node points to the next node.\n- You need to find the middle node of the linked list. If there are two middle nodes, return the second one.\n\n\n#  Step-by-Step Approach 1:\n- **Step 1:** Calculate the Length of the Linked List\n\n    - The function length(`ListNode* head`) is used to calculate the total number of nodes in the linked list.\n    - It starts at the head of the list and iterates through each node, incrementing a counter (`len`) until it reaches the end (`head` becomes `NULL`).\n    - The length of the list is then returned.\n\n- **Step 2:** Find the Middle Position\n\n    - In the `middleNode(ListNode* head)` function, the length of the linked list is obtained by calling the length(head) function.\n    - The middle position is calculated using `len / 2`. For example, if the list has 5 nodes, the middle position is `5 / 2 = 2` (since we start counting from 0).\n\n- **Step 3:** Traverse to the Middle Node\n\n    - A pointer (`temp`) is set to the head of the list.\n    - The code then traverses the list, moving the pointer from node to node until it reaches the middle position (calculated in Step 2).\n    - The middle node is then returned.\n\n`Upvote! It only takes 1 click\uD83D\uDE09`\n# Example:\nLet\'s say we have the linked list `1 -> 2 -> 3 -> 4 -> 5`.\n\n- Step 1: Length is calculated as 5.\n- Step 2: Middle position is `5 / 2 = 2`.\n- Step 3: We move the pointer 2 steps from the head, reaching the node with value `3`.\n\nThe node with value `3` is the middle node, so it\'s returned.\n# Complexity\n- Time complexity: `O(n)`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(1)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`Upvote! It only takes 1 click\uD83D\uDE09`\n# Code\n```\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\n\nclass Solution {\npublic:\n    int length(ListNode* head) {\n        int len = 0;\n        while (head != NULL) {\n            len++;\n            head = head->next;\n        }\n        return len;\n    }\n    ListNode* middleNode(ListNode* head) {\n        int len = length(head);\n        int ans = (len / 2);\n        int cnt = 0;\n        ListNode* temp = head;\n\n        while (cnt < ans) {\n            temp = temp->next;\n            cnt++;\n        }\n        return temp;\n    }\n};\n```\n`Upvote! It only takes 1 click\uD83D\uDE09`\n\n# Step-by-Step Approach 2: \n1. **Initial Checks:**\n\n- The solution first checks if the linked list is empty (`head == NULL`) or has only one node (`head->next == NULL`). In either case, the head itself is returned since it is the middle node.\n\n2. **Two-Pointer Technique:**\n\n- Two pointers are used: `slow` and `fast`.\n- `slow` starts at the head of the list, and `fast` starts at the second node (`head->next`).\n\n3. Traversal:\n\n- The `fast` pointer moves twice as fast as the `slow` pointer.\n- In each iteration, `fast` moves two nodes ahead (`fast = fast->next->next`), and `slow` moves one node ahead (`slow = slow->next`).\n- This continues until `fast` can no longer move two steps forward (i.e., `fast` becomes `NULL` or has no next node).\n\n4. Result:\n\n- When `fast` reaches the end (or near the end) of the list, `slow` will be pointing at the middle node.\n- The middle node is then returned.\n\n`Upvote! It only takes 1 click\uD83D\uDE09`\n# Why This Works:\n- The `fast` pointer moves twice as fast as the `slow` pointer. So, by the time `fast` reaches the end of the list, `slow` will have traveled half the distance, ending up at the middle.\n\n# Complexity\n- Time complexity: `O(n)`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(1)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`Upvote! It only takes 1 click\uD83D\uDE09`\n# Code\n```\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    ListNode* middleNode(ListNode* head) {\n        if (head == NULL || head->next == NULL) {\n            return head;\n        }\n        ListNode* slow = head;\n        ListNode* fast = head->next;\n\n        while (fast != NULL) {\n            fast = fast->next;\n            if (fast != NULL) {\n                fast = fast->next;\n            }\n            slow = slow->next;\n        }\n        return slow;\n    }\n};\n```\n![upvote.jpeg](https://assets.leetcode.com/users/images/48b755ae-c41b-474d-966e-aa5674e41ff4_1720943081.9620614.jpeg)
['Linked List', 'Two Pointers', 'C++']