✅ [C++/Python] Simple Solutions w/ Explanation | 2-Pointers O(N) & Inplace O(1) Space Approaches
We are given a list which we need to re-order in alternate fashion like L1 -> Ln-1 -> L2 -> Ln-2...\n\n---\n\n\u2714\uFE0F Solution - I (2-Pointers using Extra 
We are given a list which we need to re-order in alternate fashion like `L1 -> Ln-1 -> L2 -> Ln-2...`\n\n---\n\n\u2714\uFE0F ***Solution - I (2-Pointers using Extra Space)***\n\nWe can solve this question easily if using extra space is allowed. The re-ordering arrangement basically consist of 1st node, then last node, then 2nd node, then 2nd last node and so on till all nodes are covered. Thus, we just put one node from the start, then one from end in an alternating fashion. In this approach -  \n\n* We first use an auxillary array to store the nodes of linked-list\n* Once the array is filled, we initialize two variables `L` and `R` which denotes the current positions on the two ends from which we need to re-order the list in alternate fashion\n* In odd iteration, we assign the next node as `arr[L]` and move the `L` pointer ahead\n* In even iteration, we assign the next node as `arr[R]` and move the `R` pointer backward\n* This will re-order the list as alternating nodes from start and end as required.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        vector<ListNode*> arr;\n        for(auto iter = head; iter; iter = iter -> next)\n            arr.push_back(iter);\n        \n\t\t// pointers to start and end of list. Re-order in alternating fashion from both end\n        int L = 1, R = size(arr)-1;\n        for(int i = 0; i < size(arr); i++, head = head -> next) \n            if(i & 1)                             // odd iteration:\n                head -> next = arr[L++];          //        - pick node from L & update L ptr\n            else                                  // even iteration\n                head -> next = arr[R--];          //        - pick node from R & update R ptr\n        \n        head -> next = nullptr;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def reorderList(self, head):\n        arr, Iter = [], head\n        while Iter:\n            arr.append(Iter)\n            Iter = Iter.next\n        \n        L, R = 1, len(arr)-1\n        for i in range(len(arr)):\n            if i & 1:\n                head.next = arr[L]\n                L += 1\n            else:\n                head.next = arr[R]\n                R -= 1\n            head = head.next\n        head.next = None\n```\n\n***Time Complexity :*** <code>O(N)</code>, where `N` is the number of nodes in the linked list. We traverse linked list once and store it in array. Then we traverse the array once. Thus overall time- `O(2N) = O(N)`\n***Space Complexity :*** `O(N)`, required to store nodes of list into array\n\n---\n\n\u2714\uFE0F ***Solution - II (In-place Transformation)***\n\nIn the above solution, we are simply using two pointers, one to the start and one to the end of array. The nodes pointed by these pointers are picked in alternating manner and then these pointers are iterated in opposite directions. This **continues till they meet in the middle**, i.e, all nodes are covered in the process.\n\nBut we are using extra space in the form of array. We required array to be able to iterate the `R` pointer in the backward direction which wouldnt be possible if we directly used linked list. \n\nHowever, we can optimize the space by modifying our list to make it possible to iterate backwards from `R` pointer. We can simply reverse the 2nd half of the list which allows us to place `R` at the end and iterate backwards till the mid. Then the rest process remains similar in logic as above.\n\n* First **find the mid of linked list**. This can be done using slow & fast pointer algorithm\n* Then we **reverse the 2nd half** and place the `R` pointer at the end\n* Initialize `L` pointer to `head->next`\n* We can now simply **re-order by placing nodes from `L` and `R` pointers in alternating fashion** till they meet. \n\n\n\n**C++**\n```cpp\nclass Solution {\npublic:\n\t// 876. Middle of the Linked List - returns the mid of list using slow-fast pointer approach\n    ListNode* middleNode(ListNode* head) {\n        auto slow = head, fast = head;\n        while(fast && fast -> next)\n            slow = slow -> next,\n            fast = fast -> next -> next;            // fast moves at 2x speed\n        return slow;                                // slow ends up at mid\n    }\n\t// 206. Reverse Linked List - reverses and returns the head of reversed list\n    ListNode* reverseList(ListNode* head) {\n        ListNode *prev = nullptr;\n        while(head) {\n            auto nextNode = head -> next;           // store next node before reversing next ptr of cur\n            head -> next = prev;                    // reverse the next ptr to previous node\n            prev = head;                            // update previous node as cur\n            head = nextNode;                        // move to orignal next node\n        }\n        return prev;                                // returns head of reversed list\n    }\n    void reorderList(ListNode* head) {\n        if(!head || !head -> next) return;\n        auto mid = middleNode(head);\n        auto R = reverseList(mid), L = head -> next;\n        for(int i = 0; L != R; i++, head = head -> next)     // re-order in alternating fashion \n            if(i & 1) {                              \n                head -> next = L;\n                L = L -> next;\n            }\n            else {\n                head -> next = R;\n                R = R -> next;\n            }\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def reorderList(self, head):\n        def middleNode(head):\n            slow, fast = head, head\n            while fast and fast.next:\n                slow = slow.next\n                fast = fast.next.next\n            return slow\n        \n        def reverseList(head):\n            prev = None\n            while head:\n                nextNode = head.next\n                head.next = prev\n                prev, head = head, nextNode\n            return prev\n\n        if not head or not head.next: return\n        R, L, i = reverseList(middleNode(head)), head.next, 0\n        while L != R:\n            if i & 1:\n                head.next, L = L, L.next\n            else:\n                head.next, R = R, R.next\n            head, i = head.next, i + 1\n```\n\n***Time Complexity :*** <code>O(N)</code>, we need `O(N)` to find mid of list, another `O(N/2) = O(N)` to reverse the 2nd half and finally `O(N)` to re-order the list. Thus overall time: `O(3N) = O(N)`\n***Space Complexity :*** `O(1)`, only constant extra space is used\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---\n\n
[]