package leetcode.sort;import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;/**
* @Description: 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。示例 1:输入: 4->2->1->3
输出: 1->2->3->4
示例 2:输入: -1->5->3->4->0
输出: -1->0->3->4->5来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* @Param:  
* @return:  
* @Author: lvhong
* @Date:  
* @E-mail lvhong282@163.com
*/ 
public class lab148 {/*** Definition for singly-linked list.*  */public class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}//    public ListNode sortList(ListNode head) { //这是使用匿名函数的排序，实际上空间利用率和下面差不多，但内部内部直到用了什么操作，空间复杂度比较夸张，很大
//        if( head == null ){
//            return head;
//        }
//
//        List<ListNode> list = new LinkedList<ListNode>();
//
//        ListNode node = head;
//        while( node!=null ){
//            list.add(node);
//            node = node.next;
//        }
//
//
//        list.sort(new Comparator<ListNode>() {
//
//            @Override
//            public int compare(ListNode o1, ListNode o2) {
//                return o1.val > o2.val ? 1 : (o1.val == o2.val ? 0 : -1);
//            }
//        });
//        head = new ListNode(0);
//        ListNode r = head;
//        for (ListNode n : list) {
//            System.out.print(n.val + " ");
//            r.next = n;
//            r = n;
//        }
//        r.next = null;
//
//        return head.next;
//    }/*** @Description: 时间复杂度：O(nlogn)*                空间复杂度：O(1)  这里实际上归并时递归所产生的空间消耗是O（n+logn)但就算法本身来说空间复杂度是O（1），不使用递归时其实没有使用额外空间是内部交换（这是链表，没有像数组排序时申请额外的空间）** @Param:* @return:* @Author: lvhong* @Date:* @E-mail lvhong282@163.com*/public ListNode sortList(ListNode head) {  //return head == null ? null : mergeSort(head);}private ListNode mergeSort(ListNode head) {if (head.next == null) {return head;}ListNode p = head, q = head, pre = null;while (q != null && q.next != null) {pre = p;p = p.next;q = q.next.next;}pre.next = null;ListNode l = mergeSort(head);ListNode r = mergeSort(p);return merge(l, r);}ListNode merge(ListNode l, ListNode r) {ListNode dummyHead = new ListNode(0);ListNode cur = dummyHead;while (l != null && r != null) {if (l.val <= r.val) {cur.next = l;cur = cur.next;l = l.next;} else {cur.next = r;cur = cur.next;r = r.next;}}if (l != null) {cur.next = l;}if (r != null) {cur.next = r;}return dummyHead.next;}
}