快速排序
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
ListNode* get_tail(ListNode* head) {
while(head->next) head = head->next;
return head;
}
ListNode* sortList(ListNode* head) {
// write code here
if (!head || !head->next) return head;
auto left = new ListNode(-1), mid = new ListNode(-1), right = new ListNode(-1);
auto ltail = left, mtail = mid, rtail = right;
int val = head->val;
for (auto p = head; p; p = p->next) {
if (p->val < val) ltail = ltail->next = p;
else if (p->val == val) mtail = mtail->next = p;
else rtail = rtail->next = p;
}
// 末尾置0
ltail->next = mtail->next = rtail->next = NULL;
left->next = sortList(left->next);
right->next = sortList(right->next);
// 链表拼接
get_tail(left)->next = mid->next;
get_tail(left)->next = right->next;
return left->next;
}
};