题目

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

L₀→ L₁→ ... → L_n-1→ L_n

请将其重新排列后变为：

L₀→ L_n→ L₁→ L_n-1→ L₂→ L_n-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 * 10⁴]
• 1 <= node.val <= 1000

注意：本题与主站 143 题相同：https://leetcode-cn.com/problems/reorder-list/

题解

public void reorderList(ListNode head) {
    // 使用快慢指针找链表中点
    ListNode slow = new ListNode(0, head), fast = new ListNode(0, head);
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 待倒叙的链表
    ListNode mid = slow.next;
    // 顺序链表后置空
    slow.next = null;
    ListNode reverse = new ListNode(0), t;
    // 将后半部分链表倒置
    while (mid != null) {
        t = mid.next;
        mid.next = reverse.next;
        reverse.next = mid;
        mid = t;
    }

    // 根据题意 顺序链表肯定长度大于(节点数位奇数的时候大于)等于倒叙链表
    reverse = reverse.next;
    // 交叉合并两个链表
    while (reverse != null) {
        t = head.next;
        head.next = reverse;
        reverse = reverse.next;
        head.next.next = t;
        head = t;
    }
}