3 solutions - With stack, without stack and recursion solutions || Beats 100% !!
Code\n\n// Solution 1 - Without stack\nclass Solution {\npublic:\n    // Function to reverse the LL\n    ListNode *reverse(ListNode *head){\n        ListNode *c
# Code\n```\n// Solution 1 - Without stack\nclass Solution {\npublic:\n    // Function to reverse the LL\n    ListNode *reverse(ListNode *head){\n        ListNode *curr = head, *prev = NULL, *forward = NULL;\n        while(curr != NULL){\n            forward = curr->next;\n            curr->next = prev;\n            prev = curr;\n            curr = forward;\n        }\n        return prev;\n    }\n\n    void reorderList(ListNode* head) {\n        // Check for edge cases\n        if(head->next == NULL || head->next->next == NULL)\n            return;\n\n        // Step 1 - Find middle of the LL with slow-fast pointer approach\n        ListNode *slow = head, *fast = head, *slow_prev = NULL;\n        while(fast != NULL && fast->next != NULL){\n            slow_prev = slow;\n            slow = slow->next;\n            fast = fast->next->next;\n        }\n\n        // Step 2 - Split the LL into 2 parts from the middle \n        // and reverse the second part\n        ListNode *h1 = head, *h2;\n        if(fast == NULL){\n            h2 = reverse(slow);\n            slow_prev->next = NULL;\n        }\n        else{\n            h2 = reverse(slow->next);\n            slow->next = NULL;\n        }\n        \n        // Traverse both the LL while linking heads of both LL\n        ListNode *next1 = h1->next, *next2 = h2->next;\n        while(h1 != NULL && h2 != NULL){\n            next1 = h1->next;\n            next2 = h2->next;\n\n            h1->next = h2;\n            h2->next = next1;\n\n            h1 = next1;\n            h2 = next2;\n        }\n    }\n};\n\n// Solution 2 - With stack\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        // base case\n        if(head->next == NULL || head->next->next == NULL) \n            return ;\n        \n        // Step 1 - Find middle of the LL with slow-fast pointer approach\n        ListNode* slow= head,  *fast= head;\n        stack<ListNode*> st;\n        while(fast!=NULL && fast->next!=NULL){\n            slow= slow->next;\n            fast = fast->next->next;\n        }\n        \n        // Step 2 - Split the LL into 2 parts from the middle\n        ListNode* h2;\n        if(fast != NULL)\n            h2 = slow->next;    \n        else \n            h2 = slow;\n        \n        // Step 3 - Push the second LL into a stack so that the last element remains at top\n        while(h2!=NULL){\n            st.push(h2);\n            h2 = h2->next;  \n        }\n        fast = head;\n        \n        // Step 4 - Link the first node with the last node and then pop the stack\n        while(st.size()){ \n            h2 = fast->next; \n            fast->next = st.top();\n            st.top()->next = h2;\n            fast = h2;\n            st.pop();    \n        }\n\n        slow->next = NULL;\n    }\n};\n\n// Solution 3 - Recursion\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        //base case\n        if(head!=NULL || head->next!=NULL || !head->next->next!= NULL) \n            return;\n        \n        //Find the penultimate node i.e second last node of the linkedlist\n        ListNode* penultimate = head;\n        while (penultimate->next->next) \n            penultimate = penultimate->next;\n        \n        // Link the penultimate node with the second node\n        penultimate->next->next = head->next;\n        head->next = penultimate->next;\n        \n        // Set the penultimate to the the last \n        penultimate->next = NULL;\n        \n        // Recursive call\n        reorderList(head->next->next);\n    }\n};\n```
['Linked List', 'Two Pointers', 'Stack', 'Recursion', 'C++']