[C++] Simple Recursive vs. Iterative Approaches Compared and Explained, ~10% Time, ~60% Space
Core ideas:\n we have to run through the list to find the penultimate, not the last node;\n once we have it, we can also access the last and we set the the seco
Core ideas:\n* we have to run through the list to find the penultimate, not the last node;\n* once we have it, we can also access the last and we set the the second node to follow the last, last to follow the head and `NULL` the penultimate;\n* after that, we call `reorderList` on the third node;\n* if the list has less than 3 elements, no point in proceeding, so we `return` (our base case);\n\nTime performance is rather low (I go more or less quadratic here), but unless you change the values and/or use a bunch of extra memory to store the most of the list in some collection, I don\'t see many other ways around than iterating through it a bunch of times; I might try the other approach later, but that is clearly less fun.\n\nThe recursive code:\n\n```cpp\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        // base case handled here\n        if (!head || !head->next || !head->next->next) return;\n        // we need to find the penultimate node in order to proceed\n        ListNode* penultimate = head;\n        while (penultimate->next->next) penultimate = penultimate->next;\n        // then we move it in the second spot\n        penultimate->next->next = head->next;\n        head->next = penultimate->next;\n        // and set penultimate to be the last\n        penultimate->next = NULL;\n        // and then we proceed with the rest, same way\n        reorderList(head->next->next);\n    }\n};\n```\n\nThe iterative code:\n\n```cpp\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        // we need to find the penultimate node in order to proceed\n        ListNode* penultimate;\n        while (head && head->next && head->next->next) {\n            penultimate = head;\n            while (penultimate->next->next) penultimate = penultimate->next;\n            // then we move it in the second spot\n            penultimate->next->next = head->next;\n            head->next = penultimate->next;\n            // and set penultimate to be the last\n            penultimate->next = NULL;\n            head = head->next->next;\n        }\n    }\n};\n```\nCould my pride stop here? Naaaah.\n\n[Improved version with the hare-based approach](https://leetcode.com/problems/reorder-list/discuss/802983/)
['Linked List', 'Recursion', 'C', 'Iterator', 'C++']