题解 | #重排链表#

快慢指针找到链表中点，并将链表划分为前后两部分，然后将前后两部分合并。

class Solution {
public:
    void reorderList(ListNode *head) {
        // 重排链表，可以用快慢指针找到链表的中间，并划分链表，然后将后边反转，然后进行两链表的合并操作
        ListNode *slow = head, *fast = head;
        if (!head || !head->next || !head->next->next) return;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 循环退出时，slow指向链表的中点处
        // 将slow后边的链表反转
        ListNode *cur = slow->next;
        slow->next = nullptr;
        ListNode *pre = slow->next;
        ListNode *post = cur->next;

        while (post) {
            cur->next = pre;
            pre = cur;
            cur = post;
            post = cur->next;
        }

        cur->next = pre;


        // cur指向后链表的链首
        // 将两链表合并
        ListNode *p = head, *q = cur;
        ListNode *tmp;
        while (p && q)
        {
            tmp = q->next;
            q->next = p->next;
            p->next = q;
            p = q->next;
            q = tmp;
        }
        return;
    }
};