37.1 (Approach 1 : recursive) | O(n)✅ | Python & C++(Step by step explanation)✅
Intuition\nThe goal is to reorder a singly-linked list such that it is in the following pattern:\n\n1. 1st node -> nth node -> 2nd node -> (n-1)th node -> 3rd n
## Intuition\nThe goal is to reorder a singly-linked list such that it is in the following pattern:\n\n1. 1st node -> nth node -> 2nd node -> (n-1)th node -> 3rd node -> (n-2)th node -> ...\n\n## Approach\n1. **Finding the Middle**: Use the "tortoise and hare" approach to find the middle of the linked list. Move `slow` one step and `fast` two steps. When `fast` reaches the end, `slow` will be at the middle.\n[141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/solutions/4661066/361-approach-1-recursive-on-python-cstep-by-step-explanation/)\n\n2. **Divide the List**: Set `h2` as the start of the second half (`slow.next`). Break the link between the first and second halves by setting `slow.next` to `None`.\n\n\n3. **Reverse the Second Half**: Reverse the second half of the linked list. Iterate through the second half and reverse the direction of the next pointers.\n[206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/solutions/4660673/342-approach-2-recursive-on-python-cstep-by-step-explanation/)\n\n4. **Merge Two Halves**: Merge the reversed second half with the first half. Alternate nodes from each half until both halves are merged.\n[21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/solutions/4660940/351-approach-1-recursive-on-python-cstep-by-step-explanation/)\n\n## Complexity\n- Time complexity: O(n), where n is the number of nodes in the linked list.\n- Space complexity: O(1) as we are reordering the list in-place.\n\n# Code(Python)\n```python\nclass Solution:\n    def reorderList(self, head: ListNode) -> None:\n        # Finding the middle of the linked list\n        slow, fast = head, head.next\n        while fast and fast.next:\n            slow = slow.next\n            fast = fast.next.next\n\n        # Divide the linked list into two halves\n        h2 = slow.next\n        tail = slow.next = None\n\n        # Reverse the second half of the linked list\n        while h2:\n            temp = h2.next\n            h2.next = tail\n            tail = h2\n            h2 = temp\n\n        # Merge two halves of the linked list\n        h1, h2 = head, tail\n        while h2:\n            temp1, temp2 = h1.next, h2.next\n            h1.next = h2\n            h2.next = temp1\n            h1, h2 = temp1, temp2\n```\n\n# Code(C++)\n```c++\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        // Finding the middle of the linked list\n        ListNode* slow = head;\n        ListNode* fast = head->next;\n        while (fast && fast->next) {\n            slow = slow->next;\n            fast = fast->next->next;\n        }\n\n        // Divide the linked list into two halves\n        ListNode* h2 = slow->next;\n        slow->next = NULL;\n        ListNode* tail = NULL;\n\n        // Reverse the second half of the linked list\n        while (h2) {\n            ListNode* temp = h2->next;\n            h2->next = tail;\n            tail = h2;\n            h2 = temp;\n        }\n\n        // Merge two halves of the linked list\n        ListNode* h1 = head;\n        h2 = tail;\n        while (h2) {\n            ListNode* temp1 = h1->next;\n            ListNode* temp2 = h2->next;\n            h1->next = h2;\n            h2->next = temp1;\n            h1 = temp1;\n            h2 = temp2;\n        }\n    }\n};\n```\n\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/0161dd3b-ad9f-4cf6-8c43-49c2e670cc21_1699210823.334661.jpeg)\n
['Linked List', 'Two Pointers', 'C++', 'Python3']