Class Solution

LeetCode_problems/Reorder_List/solution.cpp:61–100

* Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */

 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return ;
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode* newhead=slow->next;
        slow->next=NULL;
        newhead= reverse(newhead);
        head= merge(head,newhead);
          
    }
    ListNode* merge(ListNode* l1,ListNode* l2){
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode* nexthead=l1->next;
        l1->next=l2;
        l2->next=merge(nexthead,l2->next);
        return l1;
    }
    
    ListNode* reverse(ListNode* head){
        ListNode* pre=NULL;
        if(!head || !head->next)
            return head;
        ListNode* cur=head;
        ListNode* next=NULL;
        while(cur){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};