package codeTop;

/**
 * 给定一个奇数位升序，偶数位降序的链表，将其重新排序。
 *
 * 输入: 1->8->3->6->5->4->7->2->NULL
 * 输出: 1->2->3->4->5->6->7->8->NULL
 */
public class SortOddEvenList {
    class ListNode{
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode sortOddEvenList(ListNode root){
        if(root == null || root.next == null){
            return root;
        }
        ListNode oddHead = root,evenHead = root.next;
        ListNode cur1 = oddHead,cur2 = evenHead;
        //将链表分成两部分
        while(cur2 != null && cur2.next != null){
            cur1.next = cur2.next;
            cur2.next = cur2.next.next;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        //将偶数位置的链表翻转
        ListNode pre = null;
        ListNode cur = evenHead;
        ListNode next = null;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //合并两个链表
        ListNode dumpy = new ListNode(0);
        ListNode tmp =  dumpy;
        while(pre != null && oddHead != null){
            if(pre.val <= oddHead.val){
                tmp.next = pre;
                pre = pre.next;
            }else{
                tmp.next = oddHead;
                oddHead = oddHead.next;
            }
            tmp = tmp.next;
        }
        if(pre != null){
            tmp.next = pre;
        }
        if(oddHead != null){
            tmp.next = oddHead;
        }
        return dumpy.next;
    }

}