思路：
1.使用了quicksort，但效果并不好。 当序列很长，但元素的取值范围很窄时，或序列基本有序时，快排的时间复杂度退化为O(n*n)
2. 对应该题，更合理的是使用归并排序
代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head) { return quickSort(head); } ListNode *quickSort(ListNode* &head){ for (auto ptr = head; ptr; ptr = ptr->next){ if (!ptr->next) return head;// 序列有序时，停止快排，直接返回head else{ if (ptr->val > ptr->next->val) break; } } if (!head) return head; ListNode* le = new ListNode(0); ListNode* nle = new ListNode(0); ListNode* pivot = head; for (auto ptr = head->next; ptr;){ if (ptr->val <= pivot->val) insert(le, ptr); else insert(nle, ptr); } pivot->next =NULL; ListNode *newHead = quickSort(le->next); if (!newHead) newHead = pivot; else{ ListNode* le_tail = newHead; while(le_tail->next) le_tail = le_tail->next; le_tail->next = pivot; } pivot->next = quickSort(nle->next); return newHead; } inline void insert(ListNode* &head, ListNode* &ptr){ auto tmp = ptr->next; ptr->next = head->next; head->next = ptr; ptr = tmp; } };
