剑指offer77：链表排序（归并排序）

题目：
给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

输入：head = [4,2,1,3]
输出：[1,2,3,4]

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
分析：

该问题的的输入是一个链表，所以需要找一个最适合链表的排序算法。
对数组进行排序的时间复杂度为O（nlogn），常用的有堆排序，快速排序和归并排序。
如果输入的是一个数组，那么堆排序用数组实现最大堆，该排序算法每次取出其中的最大值，再调整剩余的最大堆，直到所有数字都被取出，第9章已经介绍了如何使用数组实现堆，本质就是将堆中的节点进行编号，数组下标与节点编号对应，可以根据某个数字的下标计算其父节点或子节点在数组中的下标，在数组中只需要O（1）就可以通过下标找到一个数字，但在链表中需要O（n）的时间才能根据节点的编号找到对应的节点。因此不可能直接通过链表实现堆排序，但是如果链表的长度为n就可以创建一个长度为n的数组来实现堆，但是链表的长度为n就可以创建一个长度为n的数组来实现堆，也就是说，通过O（n）的空间代价来实现堆排序。
接下来考虑快速排序，通常快速排序算法首先随机生成一个下标，并以该下标对应的值作为中间值进行分区，如果输入的是数组那么只需要O（1）的时间就能根据下标找到一个数字，如果输入的是链表那么需要O（n）的时间才能根据编号找到对应的节点，快速排序也可以考虑不用随机的中间值，而是始终以某个固定位置的值作为中间值（如链表的头或尾节点），这样可能会出现每次分区时两个子链表的大小都不均衡，从而时间复杂度退化到O(n ^2)。
归并排序如上面图对应的例子2以及代码，由于对链表进行归并排序不需要创建另外一个相同大小的链表来保存合并之后的节点，因此对链表进行进行归并排序的空间效率高，由于代码存在递归调用，递归调用栈的深度为O（logn）,空间复杂度为O（logn）。

代码：

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode l1 = new ListNode(-1);
        ListNode l2 = new ListNode(5);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(0);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        ListNode listNode = solution.sortList(l1);
        System.out.println(listNode);
    }
    public ListNode sortList(ListNode head){
//        递归终止条件，头节点为空或者头节点下一个节点为空
        if (head == null  || head.next == null){
                return head;
        }
        ListNode head1 = head;
        ListNode head2 = split(head);
        head1 = sortList(head1);
        head2 = sortList(head2);
        return merge(head1,head2);
    }

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (head1 != null && head2 !=null){
            if (head1.val <head2.val){
                cur.next = head1;
                head1 = head1.next;
            }else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        cur.next = head1 == null ? head2 : head1;
        return dummy.next;
    }
//利用快慢指针来将链表平分成两个链表
    private ListNode split(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast !=null && fast.next !=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode second = slow.next;
        slow.next = null;
        return second;
    }
}