✅Easy✨ ||C++|| Beats 100% || With Explanation||
Intuition\n Describe your first thoughts on how to solve this problem. \nThere are many ways to solve this problem like by stack, recursion, two pointer. Here w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThere are many ways to solve this problem like by stack, recursion, two pointer. Here we have used most effective by solving this question in the vector arr and rearranging the nodes as follows.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Save Addresses: Traverse the linked list and save the addresses of all nodes in a vector arr.\n\n2. Set Pointers: After saving all addresses, initialize two pointers i and j to the beginning and end of the vector respectively. Also, initialize a pointer t1 to the first element of the vector.\n\n3. Rearrange Nodes: In a loop, rearrange the pointers to reorder the list. The basic idea is to take the node pointed by j and set it as the next node of the node pointed by i, then move j backward. Next, take the node pointed by i and set it as the next node of the node pointed by j, then move i forward. Repeat this process until i becomes greater than or equal to j.\n\n4. Terminate the List: After the loop, ensure proper termination of the reordered list by setting the next pointer of the last node to nullptr.\n\nThis approach ensures that we are properly rearranging the pointers to reorder the list while traversing it just once.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\no(N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1)\n# Code\n```\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        if (!head || !head->next)\n            return; // No need to reorder for empty or single node list\n\n        vector<ListNode*> arr; // to save address of all list nodes\n        ListNode* temp = head;\n\n        while (temp != nullptr) {\n            arr.push_back(temp);\n            temp = temp->next;\n        }\n\n        int i = 0, j = arr.size() - 1;\n        while (i < j) {\n            arr[i]->next = arr[j];\n            i++;\n\n            if (i == j) break;  // Break if i and j meet\n\n            arr[j]->next = arr[i];\n            j--;\n        }\n        arr[i]->next = nullptr;\n    }\n};\n```
['C++']