Modular O(N) Time and O(1) Space C++ Solution
This was really a nice problem comprising three common smaller problems of LinkedList\n1. Find Middle Node in Linked List\n2. Reverse a Linked List\n3. Merge Tw
This was really a nice problem comprising three common smaller problems of LinkedList\n1. Find Middle Node in Linked List\n2. Reverse a Linked List\n3. Merge Two Linked List in specific manner\n\nWe can solve all three problems in O(N) Time and O(1) Space so we can solve this problem in same Time and Space Constraints.\n\n```\nclass Solution {\npublic:\n    \n    ListNode* getMid(ListNode* head)\n    {\n        ListNode *slow,*fast;\n        slow = fast = head;\n        while(fast->next!=NULL&&fast->next->next!=NULL)\n        {\n            slow=slow->next;\n            fast = fast->next->next;\n        }\n        return slow;\n        \n    }\n    \n    ListNode* getReverse(ListNode* head)\n    {\n        ListNode *cur,*prev;\n        cur=head;\n        prev = NULL;\n        while(cur!=NULL)\n        {\n            ListNode *temp = cur->next;\n            cur->next = prev;\n            prev = cur;\n            cur = temp;\n        }\n        return prev;\n    }\n    \n    void reorderList(ListNode* head) {\n        \n        //  If Linked List contains less than 3 nodes then no need to do anything.\n        if(head==NULL||head->next==NULL||head->next->next==NULL)\n            return;\n        \n        /*  \n            Get Middle Node\n            If there is two middle node then return first Middle.\n        */\n        ListNode* mid = getMid(head);\n        \n        //  Seprate the Second Half of the LinkedList\n        ListNode* secondHalf = mid->next;\n        mid->next=NULL;\n        \n        //  Reverse the Second Half of LinkedList\n        ListNode* revHalf = getReverse(secondHalf);\n        \n        //  Finally Merge in Required Manner\n        while(head!=NULL&&revHalf!=NULL)\n        {\n            ListNode* temp = head->next;\n            head->next=revHalf;\n            revHalf=revHalf->next;\n            head->next->next=temp;\n            head = temp;\n        }\n    }\n};\n```
['C']