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]

示例 2：

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

提示：

• 链表的长度范围为 [1, 5 * 104]
• 1 <= node.val <= 1000

双指针

找到链表的中间节点，将链表分成两部分，反转链表的后半部分，合并两个链表。

因为两链表长度相差不超过 1，因此直接合并即可。

class Solution {
    /**
     * 重新排序链表，将链表 L0 → L1 → ... → Ln-1 → Ln 重新排序为 L0 → Ln → L1 → Ln-1 → L2 → Ln-2 ...
     *
     * @param head 链表的头节点
     */
    public void reorderList(ListNode head) {
        // 如果链表为空，直接返回
        if (head == null) {
            return;
        }

        // 找到链表的中间节点
        ListNode mid = middleNode(head);
        ListNode l1 = head; // 链表的前半部分
        ListNode l2 = mid.next; // 链表的后半部分
        
        mid.next = null; // 将链表分成两部分
        l2 = reverseList(l2); // 反转链表的后半部分
        mergeList(l1, l2); // 合并两个链表
    }

    /**
     * 找到链表的中间节点
     *
     * @param head 链表的头节点
     * @return 链表的中间节点
     */
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 快慢指针寻找链表的中间节点。链表长度为偶数时，fast会停在倒数第二个节点上，因为它的next.next是空。
        // fast停的位置是小于等于链表长度的最大奇数长度。这样才能保证长度为偶数时，slow停在中间偏左的位置。
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next; // 慢指针每次移动一步
            fast = fast.next.next; // 快指针每次移动两步
        }
        return slow; // 返回慢指针指向的节点，即链表的中间节点。奇数长度就是中间点，偶数长度就是中间偏左的位置。
    }

    /**
     * 反转链表
     *
     * @param head 链表的头节点
     * @return 反转后的链表头节点
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null; // 前一个节点
        ListNode curr = head; // 当前节点
        // 逐步反转链表
        while (curr != null) {
            ListNode nextTemp = curr.next; // 保存下一个节点
            curr.next = prev; // 当前节点的 next 指向前一个节点
            prev = curr; // 前一个节点更新为当前节点
            curr = nextTemp; // 当前节点更新为下一个节点
        }
        return prev; // 返回反转后的新头节点
    }

    /**
     * 迭代交叉合并两个链表，也可以递归
     *
     * @param l1 第一个链表的头节点
     * @param l2 第二个链表的头节点
     */
    public void mergeList(ListNode l1, ListNode l2) {
        ListNode l1_tmp; // 临时保存 l1 的下一个节点。只是定义，并没有初始化。
        ListNode l2_tmp; // 临时保存 l2 的下一个节点
        
        // 交替合并两个链表。结束条件是重点。
        // 根据题意，l1的长度一定大于等于l2的长度，且最多多1个节点。正因如此，我们才可以这样写while的结束条件。
        // 即l1和l2要么同时为空，要么一个为空，另一个只剩一个节点。
        while (l1 != null && l2 != null) {
            l1_tmp = l1.next; // 保存 l1 的下一个节点
            l2_tmp = l2.next; // 保存 l2 的下一个节点

            l1.next = l2; // l1 的 next 指向 l2
            l1 = l1_tmp; // l1 移动到下一个节点

            l2.next = l1; // l2 的 next 指向 l1
            l2 = l2_tmp; // l2 移动到下一个节点
        }
    }
    
    /**
     * 递归合并两个链表，将第二个链表的节点交替插入第一个链表。
     *
     * @param l1 第一个链表的头节点（主链表）
     * @param l2 第二个链表的头节点（插入链表）
     */
    public void mergeList(ListNode l1, ListNode l2) {
        // 递归结束条件：当l2为空时，不需要再进行合并
        if (l1 == null || l2 == null) {
            return;
        }

        // 保存 l1 和 l2 的下一个节点
        ListNode l1Next = l1.next;
        ListNode l2Next = l2.next;

        // 将 l2 插入到 l1 后面。两步操作
        l1.next = l2;
        l2.next = l1Next;

        // 递归处理剩余部分
        mergeList(l1Next, l2Next);
    }
}

• 时间复杂度：O(N)，其中 N 是链表中的节点数。
• 空间复杂度：O(1)。