//    ==>排序奇升偶降链表
//    给定一个奇数位升序，偶数位降序的链表，将其重新排序。
//    输入: 1->8->3->6->5->4->7->2->NULL
//    输出: 1->2->3->4->5->6->7->8->NULL
public static ListNode sortList(ListNode head){
    // 首先拆分奇偶链表
    ListNode dumyOdd = new ListNode(-1);
    ListNode odd = dumyOdd;
    ListNode dumyEven = new ListNode(-1);
    ListNode even = dumyEven;
    ListNode now = head;
    while(now != null){
        if((now.val % 2) != 0){
            odd.next = now;
            odd = odd.next;
        }else{
            even.next = now;
            even = even.next;
        }
        now = now.next;
    }
    odd.next = null;// 将尾节点置为null
    even.next = null;// 将尾节点置为null
    // 接着翻转偶数链表
    even = reverseList(dumyEven.next);
    odd = dumyOdd.next;
    // 最后合并奇偶链表
    return mergeList(odd, even);
}

private static ListNode reverseList(ListNode head){
    ListNode pre = null, now = head;
    while(now != null){
        ListNode temp = now.next;
        now.next = pre;
        pre = now;
        now = temp;
    }
    return pre;
}

private static  ListNode mergeList(ListNode odd, ListNode even){
    ListNode dumyList = new ListNode(-1);
    ListNode now = dumyList;
    while(odd != null || even != null){
        if(odd == null){
            now.next = even;
            even = even.next;
        }else if(even == null){
            now.next = odd;
            odd = odd.next;
        }else{
            if(even.val <= odd.val){
                now.next = even;
                even = even.next;
            }else{
                now.next = odd;
                odd = odd.next;
            }
        }
        now = now.next;
    }
    return dumyList.next;
}