[数据结构与算法]单链表排序

描述
给定一个无序单链表，实现单链表的排序(按升序排序)。
示例1
输入：
[1,3,2,4,5]
复制
返回值：
{1,2,3,4,5}

最简单的方法，遍历链表写到List中，sort，再拼接
下面是用归并排序的解法：

public class 单链表排序 {
     public class ListNode {
        int val;
        ListNode next = null;

         public ListNode(int val) {
             this.val = val;
         }
     }
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head==null||head.next==null){
            return head;
        }
        ListNode slow=head;
        ListNode faster=head.next;
        while(faster!=null&&faster.next!=null){
            slow=slow.next;
            faster=faster.next.next;
        }
        ListNode mid=slow.next;
        slow.next=null;

        ListNode left=sortInList(head);
        ListNode right=sortInList(mid);
        ListNode tail=new ListNode(-1);
        ListNode temp=tail;
        while(left!=null&&right!=null){
            if(left.val>=right.val){
                temp.next=right;
                right=right.next;
            }else{temp.next=left;

                left=left.next;

            }
            temp=temp.next;
        }
        if(temp!=null)
            temp.next=(left!=null)?left:right;
        return tail.next;

    }
}