题解 | #重排链表# 快慢指针+合并

• 可以把链表分成两个部分，前半和后半
• 反转后半，再合并即可
• 快慢指针找到中间的节点，然后前半的第一个指向后半的第一个，后半的第一个指向前半的第二个

class Solution {
public:
	//快慢指针找中点
    ListNode* findmid(ListNode* head)
    {
        ListNode *fast=head;
        ListNode *slow=head;
        while(fast->next!=nullptr && fast->next->next!=nullptr)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
    
    //反转链表
    ListNode *reverse(ListNode *head)
    {
        ListNode *pre=nullptr;
        ListNode *cur=head;
        while(cur)
        {
            ListNode *nxt=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }

    //合并链表
    void merge(ListNode *l1, ListNode *l2)
    {
        ListNode *tmp1;
        ListNode *tmp2;
        while(l1 && l2)
        {
            tmp1=l1->next;
            tmp2=l2->next;
            l1->next=l2;
            l1=tmp1;
            l2->next=l1;
            l2=tmp2;
        }
    }

    void reorderList(ListNode* head) {
        if(head==nullptr || head->next==nullptr)
            return;
        ListNode *mid=findmid(head);
        ListNode *l1=head;
        ListNode *l2=mid->next;
        mid->next=nullptr;
        l2=reverse(l2);
        merge(l1, l2);
    }
};