[C++] Hare-based Solution Explained, ~100% Time, ~60% Space
This was a complex one for me, since I never reverted a listed string in-place and could not focus enough for a while to spot silly mistakes.\n\nAnyway, much mo
This was a complex one for me, since I never reverted a listed string in-place and could not focus enough for a while to spot silly mistakes.\n\nAnyway, much more efficiently than [my other attempt](https://leetcode.com/problems/reorder-list/discuss/801842/C%2B%2B-Simple-Recursive-vs.-Iterative-Approaches-Compared-and-Explained-~10-Time-~60-Space), this solution delivers good results and goes in linear time (the previous was quadratic), moving from ~1000ms down up to 28ms, with 40-50ms on average.\n\nThis solution can be divided in 3 steps:\n* finding the first half of the array with the hare approach (ie: having 2 iterators parse it, one moving at double speed and thus when it will be finished, the other has to be midway) and possibly adjusting it with lists of even length;\n* reverting the list from `half` up to the end - the part that gave me a non-indifferent pain, since I was dumb, period. More info on linked list reversal [here](https://leetcode.com/problems/reverse-linked-list/discuss/803955/);\n* merging the first half starting with `head` together with the reverted second part starting with `half`, this time having to close things in case we were dealing with an even-lengthed list.\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        // exiting for empty lists\n        if (!head) return;\n        // finding the central node with the hare approach\n        ListNode *tmp = head, *half = head, *prev = NULL;\n        while (tmp->next && tmp->next->next) {\n            tmp = tmp->next->next;\n            half = half->next;\n        }\n        // adding one bit in case of lists with even length\n        if (tmp->next) half = half->next;\n        // reversing the second half\n        while (half) {\n            tmp = half->next;\n            half->next = prev;\n            prev = half;\n            half = tmp;\n        }\n        half = prev;\n        // merging the 2 lists\n        while (head && half) {\n            tmp = head->next;\n            prev = half->next;\n            head->next = half;\n            half->next = tmp;\n            head = tmp;\n            half = prev;\n        }\n        // closing when we had even length arrays\n        if (head && head->next) head->next->next = NULL;\n    }\n};\n```
['Linked List', 'C', 'C++']