题解 | #重排链表，时间O(n) , 空间O(1)#

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null) return  ;
        ListNode fast = head ;
        ListNode slow = head ;//使用快慢指针，寻找分界点
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next ;
            slow = slow.next ;
        }
        ListNode rightPart = slow.next ;//分界点
        slow.next = null ;//链表从分界点断开
        rightPart = reverse(rightPart) ;//将右边部分翻转
        ListNode l1 = head ;//左边部分的头结点
        ListNode l2 = rightPart ;//右边部分的头结点
        while(l1 != null && l2 != null) {//把右边部分的节点依次插入左边的节点之后
            ListNode tmp = l2 ;
            l2 = l2.next ;
            tmp.next = l1.next ;
            l1.next = tmp ;
            l1 = l1.next.next ;
        }
    }
    //翻转链表
    public ListNode reverse(ListNode head) {
        if(head == null) return head ;
        ListNode pre = new ListNode(-1) ;//辅助节点
        ListNode cur = head ;
        ListNode nxt = null ;
        while(cur != null) {
            nxt = cur.next ;
            cur.next = pre ;
            pre = cur ;
            cur = nxt ;
        }
        head.next = null ;//删除辅助节点
        return pre ;
    }
}