C++ easy clean code with explaination | O(n) time and O(1) space
This problem can be broken down into three simple sub problems and can be solve sequentially to arrive at our final solution.\n1. Finding the mid: take slow and
This problem can be broken down into three simple sub problems and can be solve sequentially to arrive at our final solution.\n**1. Finding the mid:** take slow and fast ptr and find the start of the second half of Linked List\n**2. Reverse Linked List:** reverse the second half and split the original Linked list into two independent linked list\n**3. Merge Linked List:** take each node one by one from both the sublists and merge them into single linked list.\n```\nclass Solution {\npublic:\n    ListNode* reverse(ListNode* head)\n    {\n        ListNode* prev=NULL;\n        ListNode* curr=head;\n        ListNode* nxt=NULL;\n        \n        while(curr)\n        {\n            nxt=curr->next;\n            curr->next=prev;\n            prev=curr;\n            curr=nxt;\n        }\n        return prev;\n    }\n    \n    void reorderList(ListNode* head) {\n        \n        //step 1 - using slow and fast pointer approach to find the mid of the list\n        ListNode* slow=head;\n        ListNode* fast=head->next;\n        \n        while(fast and fast->next)\n        {\n            slow=slow->next;\n            fast=fast->next->next;\n        }\n        \n        //step 2 - reverse the second half and split the List into two.\n        ListNode* second=reverse(slow->next); // independent list second\n        slow->next=NULL;\n        ListNode* first=head; // independent list first\n        \n        //step 3 - merging the two list\n        // second list can be shorter when LL size is odd\n        while(second)\n        {\n            ListNode* temp1=first->next;\n            ListNode* temp2=second->next;\n            first->next=second;\n            second->next=temp1;\n            first=temp1;\n            second=temp2;\n        }\n    }\n};\n```\nExample:\n**A. for odd length List**\n1, 2, 3, 4, 5\nslow ptr= 3\nreverse(4)\nsublist1 = 1, 2, 3\nsublist2 = 5, 4\nafter merge 1, 5, 2, 4, 3\n\n**B, for even length List**\n1, 2, 3, 4\nslow ptr= 2\nreverse(3)\nsublist1 = 1, 2\nsublist2 = 4, 3\nafter merge 1, 4, 2, 3
['C', 'C++']