一.题目介绍

1.题目来源

链接：LeetCode

2.题目

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

示例 1：

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

输出：[1,2,3,4]

示例 2：

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

输出：[-1,0,3,4,5]

示例 3：

输入：head = []

输出：[]

二.具体实现

1.实现思路

首先判断链表的内容是否为空，如果为空的话直接返回Null，再根据比较排序法，用前面一个的值和后面一个的值进行比较，如果后面的值小于前面的值，那么前面的一个值放到后面的位置，将后面的位置放入到前面的位置；最后返回的就是头节点head。

2.实现代码

1)自己的实现方式

public ListNode sortList(ListNode head) {
    ListNode temp=head;
    if(head==null)return null;
    while(temp.next!=null){
        ListNode cur=temp.next;
        while(cur!=null){
            if(temp.val>cur.val){
                int k=temp.val;
                temp.val=cur.val;
                cur.val=k;
            }
            cur=cur.next;
        }
        temp=temp.next;
    }
    return head;
}
复制代码

2)题友的实现方式

归并排序:找到当前链表中点，并从中点将链表断开（以便在下次递归cut时，链表片段拥有正确边界），然后再将两个排序链表合并，转化为一个排序链表

3.运行结果

三.题后思考

这个题目有点麻烦，如果是使用的暴力法，会直接超时，使用自顶向下的归并排序的话，其实也没有多大的提升，目前是没有好的解决方案的，后期继续思考吧。