143. 重排链表

寻找链表中点 + 链表逆序 + 合并链表

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* midnode = head;
        ListNode* fast  =head;
        while(fast != nullptr && fast->next != nullptr){
            midnode = midnode->next;
            fast = fast->next->next;
        }
        ListNode* left = head;
        ListNode* right = midnode->next;
        midnode->next  = nullptr;

        ListNode*pre = nullptr;
        ListNode*cur = right;
        while(cur != nullptr){
            ListNode* node = cur->next;
            cur->next = pre;
            pre = cur;
            cur = node;
        }
        right = pre;

        //ListNode* res = left;
        while(left->next != nullptr && right!=nullptr){
            ListNode* nextnode = left->next;
            left->next = right;
            right= right->next;
            left->next->next = nextnode;
            left=left->next->next;
        }
       // return res;
    }
};