题解 | #单链表的排序#

相当于就是使用选择排序的，有几个关键点，1、就是使用一个dummy节点来记录每轮最小的元素，2、每次选择出一个最小的元素，然后将这个元素在head链表中剔除，这一步是必须要做的，不然排序就永远不可以结束，而且这样也可以减少排序的复杂度，3、注意删除已选中的节点时，需要保存两个信息：当前遍历节点的前置节点、已选中节点的前置节点，这样才能保证删除的正确性，4、需要注意几个细节：可能存在head节点就是最小的节点，所以在判断时需要预先判断一下是否和当前head一致，如果一致需要将head后推一个节点

   public ListNode sortInList(ListNode head) {
        ListNode dummy = new ListNode(-1), curd = dummy;
        while (head != null) {
            ListNode curSmallest = findSmallestNode(head);
            if (curSmallest == null) {
                return dummy.next;
            }
            if (curSmallest.equals(head)) {
                head = head.next;
            }
            curd.next = curSmallest;
            curd = curd.next;
        }
        return dummy.next;
    }

    private ListNode findSmallestNode(ListNode head) {
        ListNode sm = head, headPre = null, smPre = null;
        while (head != null) {
            if (sm.val > head.val) {
                smPre = headPre;
                sm = head;
            }
            headPre = head;
            head = head.next;
        }
        if (smPre != null) {
            smPre.next = sm.next;
            sm.next = null;
        }
        return sm;
    }