Java 100% | Two-pointer approach | Explained
Explanation:\n\nIn this question we need to find the middle element of a linked list of size N.\nMiddle Element = N/2 or N/2+1\n\nFirst Approach: Using Two Pass
***Explanation:***\n\nIn this question we need to find the middle element of a linked list of size N.\nMiddle Element = N/2 or N/2+1\n\n**First Approach:** Using Two Passes \n1. Iterate over the whole linked list and find the length of the linked list, say N.\n2. Then, iterate till N/2+1 in case of odd number of nodes and N/2 in case of even number of nodes. \nIn this case Time Complexity will be O(N) and Space Complexity will be O(1).\n\n**Alternative Approach:** Using Extra Space\n1. Iterate over the whole linked list and store the data in an ArrayList.\n2. Then find the element by accessing the N/2 index of the ArrayList. \nIn this case Time Complexity and Space Complexity will be O(N).\n\n\n**Second Approach:**  Using Two pointers\n\nLet\'s think of a scenario where you have a field 200m long and there are two people, A is running with 1x speed and B is running with 2x, so at any given point A will be at half of what B has reached.\n\nSay both starts at 0m, when Person B reaches 50m then Person A will be at 25m. When Person B reaches 100m then Person A will be at 50m.\n\nAfter sometime If Person B reaches 200m then Person A will be at 100m. \nHence Person A is at mid of the field, when B reaches the end.\n\nIn order to solve this problem, we are going to use Two pointers, one pointer which moves with 1x speed and another one with 2x speed.\n\nIn this case Time Complexity will be O(N) and Space Complexity will be O(1).\n\n```\nclass Solution {\n    public ListNode middleNode(ListNode head) {\n        ListNode slow = head;\n        ListNode fast = head;\n\n        while(fast != null && fast.next != null) {\n            slow = slow.next;\n            fast = fast.next.next;\n        }\n        return slow;\n    }\n}\n```
['Linked List', 'Two Pointers', 'Java']