Fast & slow find mid & reverse & merge 2 lists vs deque vs Recursion||15ms Beats 98.75%
Intuition\n Describe your first thoughts on how to solve this problem. \nSeveral days about linked lists.\nTry pure linked list solution\nOther approaches will 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSeveral days about linked lists.\nTry pure linked list solution\nOther approaches will be added. 2nd approach use a deque; 3rd one is a very short recursive code which is very tricky & fast.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn English subtitles if neccessary]\n[https://youtu.be/20M4vc9rGVc?si=vUN-qvyeuDwrOe8W](https://youtu.be/20M4vc9rGVc?si=vUN-qvyeuDwrOe8W)\nusing Floyd\'s tortoise and hare algorithm.(Like in [Leetcode 234. Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/solutions/4908086/fast-slow-then-reverse-slow-vs-recursion-137ms-beats-96-66/))\n1. Set 2 pointers `slow` & `fast` with strides 1 & 2. Tranverse til `fast` reaching the end.\n![hase_turtle.png](https://assets.leetcode.com/users/images/e748c0d8-f5b5-4a6b-a183-60aa6bdab5cc_1711164614.1751947.png)\n\n2.  Use the same function `reverseList` (in [ Leetcode 206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/solutions/4904066/beats-100-easy-reverse-linked-list-explain-with-figure/)) to reverse `slow` as `prev`![reverseLN.png](https://assets.leetcode.com/users/images/63b66dd9-1064-4587-a706-9d16e7870212_1710993501.6268916.png)\n3. Merge both lists `A=head` & `B=prev`\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n# C/Python/C++ Code using Floyd\'s tortoise and hare, reverse & merge 2 lists||C++ 15ms Beats 98.75%||C 12ms\n```C []\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     struct ListNode *next;\n * };\n */\n#pragma GCC optimize("O3", "unroll-loops")\ntypedef struct ListNode ListNode;\nvoid reorderList(struct ListNode* head) {\n    if (!head || !head->next || !head->next->next) return;\n\n    // Find the middle of the list\n    ListNode *slow = head, *fast = head;\n    while (fast->next && fast->next->next) {\n        slow=slow->next;\n        fast=fast->next->next;\n    }\n\n    // Reverse the second half of the list\n    ListNode *prev =NULL, *cur=slow->next, *Next;\n    while (cur) {\n        Next=cur->next;\n        cur->next=prev;\n        prev=cur;\n        cur=Next;\n    }\n    slow->next=NULL;\n\n    // Merge the 2 halves\n    ListNode *A = head, *B=prev;\n    while (A && B) {\n        ListNode* A_next=A->next;\n        ListNode* B_next=B->next;\n\n        A->next=B;\n        B->next=A_next;\n\n        A=A_next;\n        B=B_next;\n    }  \n}\n```\n```python []\n# Definition for singly-linked list.\n# class ListNode:\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution:\n    def reorderList(self, head: Optional[ListNode]) -> None:\n        """\n        Do not return anything, modify head in-place instead.\n        """\n        if not head or not head.next or not head.next.next: return\n\n        # Find the middle of the list\n        slow, fast=head, head\n        while fast.next and fast.next.next:\n            slow=slow.next\n            fast=fast.next.next\n\n        # Reverse the second half of the list\n        prev=None\n        cur=slow.next\n        while cur:\n            Next=cur.next\n            cur.next=prev\n            prev=cur\n            cur=Next\n        slow.next=None\n\n        # Merge the 2 halves\n        A, B=head, prev\n        while A and B:\n            A_next=A.next\n            B_next=B.next  \n\n            A.next=B\n            B.next=A_next\n\n            A=A_next\n            B=B_next    \n```\n```C++ []\n\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        if (!head || !head->next || !head->next->next) return;\n\n        // Find the middle of the list\n        ListNode *slow = head, *fast = head;\n        while (fast->next && fast->next->next) {\n            slow=slow->next;\n            fast=fast->next->next;\n        }\n\n        // Reverse the second half of the list\n        ListNode *prev =NULL, *cur=slow->next, *Next;\n        while (cur) {\n            Next=cur->next;\n            cur->next=prev;\n            prev=cur;\n            cur=Next;\n        }\n        slow->next=NULL;\n\n        // Merge the 2 halves\n        ListNode *A = head, *B=prev;\n        while (A && B) {\n            ListNode* A_next=A->next;\n            ListNode *B_next=B->next;\n\n            A->next=B;\n            B->next=A_next;\n\n            A=A_next;\n            B=B_next;\n        }\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ using deque||24ms Beats 59.39%\n\nUsing container deque is easily to show the process. Let\'s consider the testcase `[1,2,3,4,5,6,7,8,9,10,11,12]`\nThe process is as follows:\n```\nCreat q from head->next on:2,3,4,5,6,7,8,9,10,11,12,\npop_back, pop_front->3,4,5,6,7,8,9,10,11,\npop_back, pop_front->4,5,6,7,8,9,10,\npop_back, pop_front->5,6,7,8,9,\npop_back, pop_front->6,7,8,\npop_back, pop_front->7,\n```\n```\nclass Solution {\npublic:\n    void print(auto& q){\n        for(auto& l: q) cout<<l->val<<",";\n        cout<<endl;\n    }\n    void reorderList(ListNode* head) {\n        if (!head || !head->next || !head->next->next) return;\n        \n        deque<ListNode*> q;\n        for(ListNode* cur=head->next; cur; cur=cur->next)\n            q.push_back(cur);\n    //    cout<<"Creat q from head->next on:";print(q);\n\n        ListNode* cur=head;\n        while(q.size()>=2){\n            ListNode* back=q.back(), *front=q.front();\n            q.pop_back();\n            q.pop_front();\n\n            cur->next=back;\n            back->next=front;\n            cur=front;\n        //    cout<<"pop_back, pop_front->"; print(q); \n        }\n\n        if (!q.empty()) {\n            cur->next = q.back();\n            cur->next->next = NULL;\n        } \n        else \n            cur->next=NULL;\n        q.clear();\n    }\n};\n```\n# Recursive C++, python||C++ 17ms Beats 95.65%\nThe recursive solution is tricky which uses system stack. By successive recursive calling the function `transverse(right->next, cnt+1)`, in fact the `right` behaves like a backward transverse as the parameter in  `transverse(ListNode* right, int cnt)`; using `n=max(n, cnt+1)` in the recursive function it can be computed the length for the list. \n\nJust see the process by uncommenting the output for testcase `[1,2,3,4,5,6,7,8,9,10,11,12]`\n(1,12) cnt=12\n(2,11) cnt=11\n(3,10) cnt=10\n(4,9) cnt=9\n(5,8) cnt=8\n(6,7) cnt=7\n```C++ []\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    ListNode* left;\n    int n=0;\n    void transverse(ListNode* right, int cnt){\n        if (!right) return;\n        n=max(n, cnt+1);\n        transverse(right->next, cnt+1);\n   \n        if (cnt<= n/2) return;//most tricky part\n\n        // cout<<"("<<left->val<<","<<right->val<< ")cnt="<<cnt<<endl;\n        ListNode* Next = left->next;\n        left->next = right;\n        right->next = Next;\n        left = Next;\n    }\n\n    void reorderList(ListNode* head) {\n        if (!head || !head->next || !head->next->next) return;\n\n    //    n=1;\n    //    for(ListNode* cur=head; cur; cur=cur->next) n++;\n            \n        left=head;\n        transverse(head->next, 2);\n        left->next=NULL;\n    }\n};\n\n```\n```python []\n# Definition for singly-linked list.\n# class ListNode:\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution:\n    def reorderList(self, head: Optional[ListNode]) -> None:\n        """\n        Do not return anything, modify head in-place instead.\n        """\n        left=None\n        n=0 \n        def transverse(right, cnt):\n            nonlocal n, left\n            if not right: return\n            n=max(n, cnt+1)\n            transverse(right.next, cnt+1)\n\n            if cnt<=n//2: return\n\n            Next=left.next\n            left.next=right\n            right.next=Next\n            left=Next\n\n        if not head or not head.next or not head.next.next: return\n        left=head\n        transverse(head.next, 2)\n        left.next=None \n        \n```\n\n
['Linked List', 'Two Pointers', 'Recursion', 'Queue', 'C', 'C++', 'Python3']