Try this strange solution **NOT INPLACE REORDERING** c++
IntuitionThe problem requires us to reorder a linked list such that nodes are arranged in the following pattern:
1st → last → 2nd → second last → 3rd → ... and
# Intuition
The problem requires us to reorder a linked list such that nodes are arranged in the following pattern:
1st → last → 2nd → second last → 3rd → ... and so on.

To achieve this, we need to access the last nodes efficiently. A stack (LIFO structure) helps store the nodes in reverse order, allowing us to pop elements in the required sequence.
# Approach
1) Store Nodes in a Stack:

* Traverse the linked list and push all nodes onto a stack.
* This allows us to access the last node first (LIFO order).
Reorder the List:

2) Start from the head node (t2 = head).
* Iteratively pop elements from the stack and insert them between the current node and its next node.
* Stop when we reach the middle of the list.
3) Handle the Last Node:

* Ensure the last node points to nullptr to avoid cyclic connections.
# Complexity
- Time complexity:
O(N)
- Space complexity:
O(N)
# Code
```cpp []
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return; // Edge cases
        
        ListNode* t = head;
        stack<ListNode*> st;

        // Push all nodes onto the stack
        while (t) {
            st.push(t);
            t = t->next;
        }

        ListNode* t2 = head;
        int n = st.size();
        
        // Reordering process
        for (int i = 0; i < n / 2; i++) {
            ListNode* top = st.top();
            st.pop();

            top->next = t2->next;
            t2->next = top;
            t2 = top->next;
        }

        // Ensure the last node points to NULL to avoid cycles
        if (t2) t2->next = nullptr;
    }
};

```
['C++']