/*
1. 把后小半段提取出来, 翻转, 间隔插入前半段

*/



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {

        if (head == null || head.next == null) return ;
        int n = getLength(head);
        int m = (n) >> 1;
        p = head;
        while (m -- != 0) p = p.next;
        ListNode h2 = p.next;
        p.next = null;
        h2 = reverse(h2);
        merge(head, h2);
    }

    int getLength(ListNode head){
        int n = 0;
        ListNode p = head;
        while (p != null){
            n++;
            p = p.next;
        }
        return n;
    }

    ListNode reverse(ListNode head){
        if (head == null || head.next == null) return head;

        ListNode p1 = head, p2 = head.next;

        while (p1 != null && p2 != null){
            ListNode p = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p;
        }
        head.next = null;

        return p1;
    }

    void print(ListNode h){
        while (h != null) {
            System.out.printf("%d ", h.val);
            h = h.next;
        }
        System.out.println();
    }

    void merge(ListNode l1, ListNode l2){

        ListNode p1 = l1, p2 = l2;

        while (p1 != null && p2 != null){
            ListNode next = p2.next;
            insert(p1, p2);
            if (p1 != null) p1 = p1.next;
            if (p1 != null) p1 = p1.next;
            p2 = next;
        }
    }

    void insert(ListNode base, ListNode p){
        p.next = base.next;
        base.next = p;
    }
}