sort list(给链表排序)

Sort a linked list in O(n log n) time using constant space complexity.

题目要求使用O(nlogn)时间复杂度，可以考虑使用归并排序，在  merge two sorted lists 中，已经知道了将两个有序链表进行合并。这里只要在这基础上修改。

排序算法入门之归并排序（java实现） 说了数组的归并排序，

使用归并排序。每次要找到中间元素进行前后的排序，然后进行合并。
合并时，数组是使用一个额外的空数组，因为使用一个数组要用到插入，数组操作插入不方便。
对于链表合并，可以使用一个额外的链表。也可以不使用额外链表，使用两个合并链表中的一个，将合并后元素都放到该链表中，因为链表操作插入方便。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
    使用归并排序。每次要找到中间元素进行前后的排序，然后进行合并。
    合并时，数组是使用一个额外的空数组，因为使用一个数组要用到插入，数组操作插入不方便。
    对于链表合并，可以使用一个额外的链表。也可以不使用额外链表，使用两个合并链表中的一个，将合并后元素都放到该链表中，因为链表操作插入方便。
    */
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
    public ListNode mergeSort(ListNode head){
        if(head==null||head.next==null) return head;
        //找到中间节点,然后将链表断开，分成两个链表
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //将链表断开，分成两个
        ListNode head2=slow.next;
        slow.next=null;//断开
        ListNode head1=head;
        head1=mergeSort(head1);
        head2=mergeSort(head2);
        return merge(head1,head2);
        
    }
    //这里合并时，不使用额外的链表,使用l1作为保存结果，但是因为l1的第一个元素可能会发生改变，所以新建一个节点
    public ListNode merge(ListNode l1,ListNode l2){
        ListNode helper=new ListNode(0);
        helper.next=l1;
        ListNode pre=helper;//指向l1节点的前一个节点，用于插入节点到l1前面
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                l1=l1.next;
            }else{
                ListNode next=l2.next;
                l2.next=l1;
                pre.next=l2;
                l2=next;
                
            }
            pre=pre.next;
        }
        while(l2!=null){
            pre.next=l2;
            pre=pre.next;
            l2=l2.next;
        }
        return helper.next;
    }
}