Two Approaches✅|| Using Stack & Tortoise and Hare method 🔥|| Easy to understand
\n Describe your first thoughts on how to solve this problem. \n\n# Approach 1: ( Using Stack)\n1. It starts by traversing the linked list and pushing each node
\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach 1: ( Using Stack)\n1. It starts by traversing the linked list and pushing each node onto a stack. This effectively reverses the order of nodes.\n2. Then it starts traversing the list again from the beginning.\n3. During this traversal, it pops a node from the stack, connects it to the current node in the traversal, and moves forward.\n4. It continues this process until it encounters a situation where the current node and the node at the top of the stack are the same, which indicates the mid-point of the list.\n5. At this point, it breaks the connection to the next node (to avoid cycles) and stops the process.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        stack<ListNode*> s;\n        ListNode* curr = head;\n        while(curr){\n            s.push(curr);\n            curr = curr->next;\n        }\n        curr = head;\n        unordered_map<ListNode*, bool> vis;\n        while(true){\n            ListNode* last = s.top();\n            s.pop();\n            ListNode* next = curr->next;\n            vis[curr] = true;\n            if(vis[last]){ \n                curr->next = NULL; \n                break; \n            } \n            curr->next = last; \n            vis[last] = true;\n            curr = curr->next; \n            if(vis[next]){\n                curr->next = NULL;\n                break;\n            }\n            curr->next = next;\n            curr = curr->next;\n        }\n    }\n};\n```\n# Approach 2: (Tortoise and Hare method)\nTwo pointer Approach Algorithm:\n\n1. First let\'s take two pointers name it as half and temp . temp is faster than half by 1.\n2. When temp reaches the end of linkedlsit half reaches the middle element .So this is how the linkedlist will get divided in two halfes as the center will become a dividing node .\n3. Now reverse the second half .\n4. After reversing the second half, merge the first half and second half.\n\n```\n//Upvote and Comment\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        // base case : linkedlist is empty\n        if (!head) return;\n        \n        // finding the middle with the help of two pointer 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        \n        // adding one bit in case of lists with even length\n        if (tmp->next) half = half->next;\n        \n        // Now reverse 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        \n        // After reversing the second half, let\'s merge both the halfes\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        \n        // Base case : closing when we had even length arrays\n        if (head && head->next) head->next->next = NULL;\n    }\n};\n```\n![bill.png](https://assets.leetcode.com/users/images/bb886228-fe23-43fc-a027-64571b0d2697_1711156389.6040218.png)\n\n
['Two Pointers', 'Stack', 'C++']