/**
 * @author wuze
 * @desc ...
 * @date 2021-07-03 00:51:57
 */

/*
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

输入：head = [4,2,1,3]
输出：[1,2,3,4]
    输入：head = [-1,5,3,4,0]
    输出：[-1,0,3,4,5]
输入：head = []
输出：[]
 */
public class 排序链表_148 {

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    class Solution {

        /*
        方法二：归并排序&递归法（结合了几道经典链表题的特点）
        思路：
        1、先将链表二分法分割成2个节点2个节点的形式（也就是归并法的前置步骤） —— 快慢指针+递归分割
        2、再递归将每组两两节点合并 —— 递归+归并合并（基于 21.合并两个有序链表，这里的合并区别在于是 递归合并，所以需要在每一个递归层连接上 上一次链表的节点（链接起来））
        3、return 新链表头结点（.next 因为最开头是伪头结点）

        */
        public ListNode sortList(ListNode head) {
            if(head==null || head.next==null){
                return head;
            }
            //////// 1、快慢指针+递归分割 ////////
            //快慢指针
            ListNode slow = head;
            ListNode fast= head.next;

            while(slow.next!=null && fast.next!=null && fast.next.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            //遍历完原链表之后，此时slow就是原链表的中点位置
            //先备份slow节点的右边节点，再把链表从slow位置将链表分割成两半
            ListNode rTmpNode = slow.next;
            slow.next=null;


            //递归分割整个链表，使都成为两个两个的节点（如果是偶数，就有剩下单独一个节点的情况）
            ListNode left = sortList(head);
            ListNode right = sortList(rTmpNode);

            //////// 2、递归+归并合并 ////////
            //再递归合并（原理跟 21.合并两个有序链表 思路一样，只是多了递归操作），抽象成一个函数来调用
            return mergeList(left,right);

        }


        /*
        递归合并（原理跟 21.合并两个有序链表 思路一样，只是多了递归操作），抽象成一个函数来调用
         */
        public ListNode mergeList(ListNode left,ListNode right){
            if(left==null || right==null){
                return null;
            }

            ListNode tmpNode = new ListNode(-1);//游标结点
            ListNode curNode = tmpNode;//备份新链表头节点
            while(left!=null && right!=null){
                if(left.val<right.val){
                    curNode.next=left;
                    left=left.next;
                }else{
                    curNode.next=right;
                    right=right.next;
                }
                curNode=curNode.next;
            }
            //关键点：
            //（坑）注意：这里需要连接，目的是为了在递归的下一层也可以将当前新链表作为base再连接上其他的排序后的节点！
            if(left!=null){
                curNode.next=left;
            }else{
                curNode.next=right;
            }

            //////// 3、return 新链表头结点 ////////
            //返回新链表节点的头结点
            return tmpNode.next;
        }






        /*
        方法一：（时间复杂度太高了）
            1、先遍历一遍原链表，把所有的节点值取出来，放在数组里
            2、对数组进行排序（升序）
            3、把排序后的数组一个个取值，去创建一个个节点
            4、将新创建的所有节点都连成一个新链表
            5、return 新链表头结点

        */
        public ListNode sortList(ListNode head) {
            //边界判断
            if(head==null || head.next==null){
                return head;
            }

            //游标节点，遍历用
            ListNode midNode=head;
            //获取链表长度
            int len=0;
            while(midNode!=null){
                len++;
                midNode=midNode.next;
            }
            //1、获取原链表每个节点值
            int arr[]=new int[len];
            midNode=head;
            for(int j=0;j<len;j++){
                arr[j]=midNode.val;
                midNode=midNode.next;
                //System.out.println(arr[j]);
            }
            //2、排序（升序）
            for(int j=0;j<arr.length;j++){
                for(int k=j+1;k<arr.length;k++){
                    if(arr[k]<arr[j]){
                        int tmp=arr[j];
                        arr[j]=arr[k];
                        arr[k]=tmp;
                    }
                }
            }

            ListNode newNode=new ListNode(-1);//游标节点，遍历用
            ListNode headNode = new ListNode(-1);//新链表头结点，return用
            headNode=newNode;

            for(int j=0;j<arr.length;j++){
                //3、取排序后数组的值，创建节点
                ListNode tmpMidNode = new ListNode(arr[j]);
                //4、连成新链表
                newNode.next=tmpMidNode;
                newNode=newNode.next;//注：自己也要向后走
            }
            return headNode.next;
        }
    }
}