143. Reorder List
Code\n\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\
# 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    ListNode* reverse(ListNode *head){\n        if(!head) return NULL;\n        ListNode *prev = NULL;\n        ListNode *curr = head;\n        ListNode *nextNode = NULL;\n        while(curr){\n            nextNode = curr->next;\n            curr->next = prev;\n            prev = curr;\n            curr = nextNode;\n        }\n        return prev;\n    }\n\n    void merge(ListNode *list1, ListNode *list2){\n        while(list2) {\n            ListNode  *nextNode = list1->next;\n            list1->next = list2;\n            list1 = list2;\n            list2 = nextNode;\n\n        }\n\n    }\n    void reorderList(ListNode* head) {\n        if(!head || !head->next) return;\n        ListNode *slow = head;\n        ListNode *fast = head;\n        ListNode *prev = head;\n        while(fast && fast->next){\n            prev = slow;\n            fast = fast->next->next;\n            slow = slow->next;\n        }\n        prev->next = NULL;\n        ListNode *list1 = head;\n        ListNode *list2 = reverse(slow);\n        merge(list1,list2);\n    }\n};\n```
['C++']