题解 | #单链表的排序#

思路

类似数组排序，链表排序也可以通过冒泡法进行实现。（简单暴力，不喜勿喷，算法小白）

冒泡法：每次将最大的数（最小的）一个数交换至序列的末端（首端）。

我们知道了一次循环可以将1个数字放置到末端保持有序，那么我们N个数就需要N次循环，这样我们需要计算整个链表的长度。

实现逻辑：
①首先定义一个链表引用，用于循环获取链表长度，也可以叫做待排序值数量
②当size大于1时，进入外层循环，每次内层循环会获取头结点的引用，根据引用，不断对前后两个结点的数值做比较，数值大的往后面进行交换，交换完毕后，引用变为下一个节点的引用，直到下一个引用为null一次循环结束，由于内层循环结束，代表已经找到一个最大的数交换到了末尾，此时size的值减一，这样不断重复上述过程，最后就得到了一个有序的链表集合。

优化点

随着末尾不断向前出现有序的序列，比较的次数也可以减少到针对未排序的数值部分。例如：0-10个数，末尾2个数有序，这个时候可以对冒泡的区间缩小为0-8，就不用每次循环都比较0-10，这样减少了比较次数，算法的执行效率会有所提高。

代码实现

public ListNode sortInList (ListNode head){
        //记录头部引用
        ListNode first = head;
        //计算链表长度
        ListNode getSize = head;
        int size=0;
        while(getSize!=null){
            size++;
            getSize = getSize.next;
        }
        //当size为1时，代表没有需要比较的区间了，整个链表已经有序
        while(size>1){
            ListNode index = first;
            //每一次循环，会将最大的数往右边进行交换，一趟循环，找到区间最大的数放置右边
            while(index!=null){
            int num1 = index.val;
            if(index.next==null){
                break;
            }
            int num2 = index.next.val;
            if(num1>num2){
                int temp = index.val;
                index.val = index.next.val;
                index.next.val = temp;
            }
            //引用下一个节点
            index = index.next;
            }
            size--;
        }
        return head;

    }