重新排列链表 考研题

题目描述：
给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：
输入: head = [1,2,3,4]
输出: [1,4,2,3]

示例 2：
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

思路：
1. 找到链表中点，将链表分为两个部分
2. 将后半部分链表翻转
3. 将两个链表合并

时间复杂度：O(n)
空间复杂度：O(1)

代码实现：

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* mid = slow->next;
        slow->next = nullptr;
        ListNode* last = nullptr;
        while (mid) {
            ListNode* next = mid->next;
            mid->next = last;
            last = mid;
            mid = next;
        }
        ListNode* cur = head;
        while (cur && last) {
            ListNode* next1 = cur->next;
            ListNode* next2 = last->next;
            cur->next = last;
            last->next = next1;
            cur = next1;
            last = next2;
        }
    }
};