Best O(N) Solution
Approach\nUsing Stack\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n\n/**\n * Definition for singly-linked list.\n * struct 
# Approach\nUsing Stack\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$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        int size = 0;\n        ListNode* dummy = head;\n        stack <ListNode*> nodes;\n        while (dummy != NULL) {\n            nodes.push(dummy);\n            size++;\n            dummy = dummy->next;\n        }\n        dummy = head;\n        for (int i = 0; i < size / 2; i++) {\n            ListNode* temp = dummy->next;\n            dummy->next = nodes.top();\n            nodes.pop();\n            dummy = dummy->next;\n            dummy->next = temp;\n            dummy = temp;\n        }\n        dummy->next = NULL;\n    }\n};\n```
['C++']