import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        //方法一：快速排序，利用辅助数组，使用数组工具类对数组排序
        //特殊值处理，当链表为空或者链表的长度为1时，直接返回原链表的头指针
//         if(head == null || head.next == null){
//             return head;
//         }
//         ListNode head0 = head;
//         ArrayList<Integer> arrayList = new ArrayList<>();//创建一个ArrayList
//         //遍历链表，将链表中的值保存在列表中
//         while (head0 != null){
//             arrayList.add(head0.val);
//             head0 = head0.next;
//         }
//         head0 = head;
//         final Object[] objects = arrayList.toArray();//将列表转换为数组
//         int len = arrayList.size();
//         int[] arr = new int[len];
//         for(int i=0;i<len;i++){//将Object[]数组转换为整型数组int[]
//             arr[i] = (int) objects[i];
//         }
//         Arrays.sort(arr);//利用数组工具类Arrays对整型数组int[]排序
//         int index = 0;
//         while (head0 != null){//将排好序的值放回到原来的链表中
//             head0.val = arr[index];
//             index++;
//             head0 = head0.next;
//         }
//         return head; //返回原链表的头指针
        
        //方法二：归并排序，使用递归，先对链表分割成长度小于3的子链表，排序，再将排好序的链表排序
        if(head == null || head.next == null){
            return head;
        }
        ListNode head0 = head;
        int count = countNode(head0);
        head0 = head;
        ListNode root = mergeSort(head0, count);
        return root;
    }
    
    /**
     * 题目描述：找出链表的中点节点
     * @param pHead  链表的头节点
     * @param len  链表节点的个数
     * @return  返回链表的中点节点的指针
     */
    public static ListNode findMiddlePosition(ListNode pHead,int len){
        int count = len/2;
        ListNode temp = pHead;
        while (count > 1){
            temp = temp.next;
            count--;
        }
        return temp;
    }
    
    /**
     * 题目描述：计算出链表节点的个数
     * @param pHead  链表的头指针
     * @return  返回链表的节点个数
     */
    public static int countNode(ListNode pHead){
        ListNode temp = pHead;
        int count = 0;  //计数器
        while (temp != null){
            count++;
            temp = temp.next;
        }
        return count;
    }
    
    /**
     * 题目描述：输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
     *          eg:1->3->5;  ==>1->2->3->4->5->6
     *             2->4->6;
     * @param list1  链表1
     * @param list2  链表1
     * @return 返回合并后的链表头节点
     */
    public static ListNode Merge(ListNode list1,ListNode list2) {
        //特殊值处理，list1为空，返回链表2的头节点
        if(list1 == null){
            return list2;
        }
        //特殊值处理，list2为空，返回链表1的头节点
        if(list2 == null){
            return list1;
        }
        ListNode head = null;//合并后的链表头节点
        //初始化头节点
        if(list1.val <= list2.val){
            head = list1;
            list1 = list1.next;
        }else {
            head = list2;
            list2 = list2.next;
        }
        ListNode head0 = head;//初始化合并后的链表的尾节点
        while (list1 != null && list2 != null){//当链表1和链表2都不为空时，比较两个链表的最小值
            if(list1.val <= list2.val){//链表1的最小值小于链表2的最小值
                head0.next = list1;  //合并后的链表的尾节点指向链表1的头节点
                head0 = head0.next;  //更新合并后的链表的尾节点
                list1 = list1.next;  //更新链表1的头节点
            }else {
                head0.next = list2;  //合并后的链表的尾节点指向链表2的头节点
                head0 = head0.next;  //更新合并后的链表的尾节点
                list2 = list2.next;  //更新链表2的头节点
            }
        }
        if(list1!=null){//当链表1不为空时，合并后的链表的尾节点指向链表1的头节点
            head0.next = list1;
        }
        if(list2!=null){//当链链表2不为空时，合并后的链表的尾节点指向链表2的头节点
            head0.next = list2;
        }
        return head;//返回合并后的链表的头节点
    }
    
    /**
     * 题目描述：合并两个链表，使得节点值顺序排序，先分割，然后排序，最后合并
     * @param pHead  链表的头节点
     * @param len  链表的长度
     * @return  返回节点值顺序排序后链表的头指针
     */
    public static ListNode mergeSort(ListNode pHead,int len){
        ListNode left = null;  //保存左边链表的头指针
        ListNode right = null;  //保存右边链表的头指针
        ListNode head0 = pHead;  //临时头指针
        if(len > 2){//当链表的长度大于2时，链表需要分割
            final ListNode middlePosition = findMiddlePosition(head0, len);//找出链表的中间位置，返回值是左边链表的尾节点
//             head0 = pHead;  //左边链表临时头指针
            right = middlePosition.next;  //保存右边链表的头指针
            middlePosition.next = null;   //切断链表
            final int leftCount = countNode(head0);  //计算左边链表的长度
//             head0 = pHead;  //左边链表临时头指针
            left = mergeSort(head0, leftCount);  //对左边链表进行合并排序
            ListNode right0 = right;    //右边链表临时头指针
            final int rightCount = countNode(right0);  //计算右边链表的长度
//             right0 = right;    //右边链表临时头指针
            right = mergeSort(right0,rightCount);   //对右边链表进行合并排序
            left = Merge(left,right);//合并两个已经排序的链表，合并后的链表值有序
            return left;  //返回归并后的链表头指针
        }
        if(len == 1){//当链表的长度等于1时，此时链表已经排好序，直接返回链表的头指针
            return pHead;
        }
        head0 = pHead;
        if(len == 2){//当链表的长度等于2时，此时需要对链表的两个节点排序，然后返回链表的头指针
            if(head0.val > head0.next.val){
                int temp0 = head0.val;
                head0.val = head0.next.val;
                head0.next.val = temp0;
            }
        }
        return pHead;
    }
}