题解 | #单链表的排序#

1.如果不限制空间大小，直接遍历一遍链表，把数据拿出来排好序后再放回原链表。空间O（n），时间可以到O（nlgn）
2.如果限制空间大小O（1）,那么可以直接在链表上进行排序，选择排序比较好写，但是时间上得到O（n*n），这道题过不了

注意：哨兵的设置，可以有效的减少不必要的操作

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(!head)
            return nullptr;
        ListNode* t = new ListNode(0); //放入开头的哨兵，减少不必要的操作
        t->next = head;
        ListNode* start = t;
        while(start->next) {
            ListNode* pre = start, * curr = start->next, * minpre = start, * min = start->next;
            while(curr) {
                if(curr->val < min->val) {
                    min = curr;
                    minpre = pre;
                }
                pre = curr;
                curr = curr->next;
            }
            minpre->next = min->next;
            min->next = start->next;
            start->next = min;
            start = start->next;
        }
        return head;
    }

};