✅ [C++/Python] Simple Solution w/ Explanation | Brute-Force + Single-Pass using Slow & Fast Pointers
We are given a linked-list and we need to return the middle node of it\n\n---\n\n\u2714\uFE0F Solution - I  (Brute-Force)\n\nWe can start with brute-force appro
We are given a linked-list and we need to return the middle node of it\n\n---\n\n\u2714\uFE0F ***Solution - I  (Brute-Force)***\n\nWe can start with brute-force approach. To return the middle node, we need to know the length of the linked-list. So, we perform the 1st iteration from start to end of linked list and count the number of nodes `N`. Then, in the next loop, we iterate till `N/2`th, i.e, the middle node and return it\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    ListNode* middleNode(ListNode* head) {\n        int N = 0;\n        for(auto iter = head; iter; iter = iter -> next, N++);   // find length \'N\' of linked-list\n        for(int i = 0; i < N/2; i++)                             // traverse till N/2th node to find the middle\n            head = head -> next;\n        return head;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def middleNode(self, head):\n        Iter, N = head, 0\n        while Iter:\n            Iter, N = Iter.next, N + 1\n        for i in range(N//2):\n            head = head.next\n        return head\n```\n\n\n***Time Complexity :*** `O(N)`, where `N`, is the number of nodes in the linked list. We traverse the complete list once to find its length which takes `O(N)` and another iteration to find its mid which takes `O(N/2) ~ O(N)`\n***Space Complexity :*** `O(1)`, only constant extra space is being used\n\n---\n\n\u2714\uFE0F ***Solution - II (Slow & Fast Pointers Approach)***\n\nThere\'s another simple approach that allows us to find the mid of linked-list in a single-pass. Here, we use two pointers - \n* `slow` which moves ahead by 1 node per iteration and,\n* `fast` which moves ahead by 2 nodes per iteration\n\nWe continue the process till fast doesn\'t reach the end of linked-list, i.e, `fast or fast -> next` is not null. Since, `fast` has reached the end of list, it has traversed `N` nodes. `slow` pointer moved at half the speed of `fast` and thus, `slow` pointer must have traversed `N/2` nodes and is currently at the middle node. So, we now simply return the `slow` pointer as middle node.\n\n```\nConsider the following linked-list\n        \uD83D\uDC0C \n1.\t  \t 1 -> 2 -> 3 -> 4 -> 5\n\t    \uD83D\uDC07 \n\t\t\n             \uD83D\uDC0C \n2.\t  \t 1 -> 2 -> 3 -> 4 -> 5\n\t              \uD83D\uDC07 \t\n\t\t\t\t  \n                  \uD83D\uDC0C \n3.\t  \t 1 -> 2 -> 3 -> 4 -> 5\n\t                         \uD83D\uDC07 \t\t        \uD83D\uDC48 \'fast\' Reached end...\n\t\t\t\t\t\t\t\t\t\t\t\t\tso \'slow\' must be now at middle node of list\n\t\t\t\t\t\t\t \n\t\t\t\t\t\t\t \nAnother example in case of even-length list.\n        \uD83D\uDC0C \n1.\t  \t 1 -> 2 -> 3 -> 4 -> 5 -> 6\n\t    \uD83D\uDC07 \n\t\t\n             \uD83D\uDC0C \n2.\t  \t 1 -> 2 -> 3 -> 4 -> 5 -> 6\n\t              \uD83D\uDC07  \n\t\t\n                  \uD83D\uDC0C \n3.\t  \t 1 -> 2 -> 3 -> 4 -> 5 -> 6\n\t                        \uD83D\uDC07 \t\t\n\n                       \uD83D\uDC0C \n3.\t  \t 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL\n\t                                   \uD83D\uDC07 \t\t\uD83D\uDC48 \'fast\' Reached end...\n\t\t\t\t\t\t\t\t\t\t\t\t\tso \'slow\' must be now at middle node of list\n\t\t\t\t\t\t\t\t\t\t\t\t\tSince, there are 2 mid, this approach returns 2nd mid node as required by question\n\t\t\t\t\t\t\t\t\t\t\t\t\tTo return 1st mid, start \'fast\' at \'head -> next\'\t\t\t\t\t\t\t\t\t\t\t\t\t\n```\n\nThis approach is known as **slow/fast pointer or floyd\'s hare & tortoise approach**. If questions such as find/delete middle node, detect cycle, palindrome linked-list, etc is asked in interview, you would be expected to solve the question using this approach.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    ListNode* middleNode(ListNode* head) {\n        auto slow = head, fast = head;\n        while(fast && fast -> next) \n            slow = slow -> next,                                  // slow moves at 1 node / iteration\n            fast = fast -> next -> next;                          // fast moves 2 nodes / iteration\n        return slow;                                              // slow ends up at mid\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def middleNode(self, head):\n        slow, fast = head, head\n        while fast and fast.next:\n            slow, fast = slow.next, fast.next.next\n        return slow\n```\n\n\n***Time Complexity :*** `O(N)`, we only traverse the list till end once\n***Space Complexity :*** `O(1)`\n\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---\n
[]