143-重排链表

LeetCode 143. 重排链表

给定一个单链表 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]

method: 模拟

先找到中间节点，反转后半条，再合并，奇数的话前半条会比后半条多一个

ListNode* reverse(ListNode *head) {
    ListNode *pre = nullptr;
    while (head) {
        ListNode *tmp = head->next;
        head->next = pre;
        pre = head;
        head = tmp;
    }
    return pre;
}
void merge(ListNode *l1, ListNode *l2) {
    while (l1 && l2) {
        ListNode *tmp1 = l1->next;
        l1->next = l2;
        l1 = tmp1;
        ListNode *tmp2 = l2->next;
        l2->next = l1;
        l2 = tmp2;
    }
}
void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode *l2 = reverse(slow->next); // 反转后半条
    slow->next = nullptr;   // 断开
    merge(head, l2);    // 合并
}