/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* quickSortList(ListNode* head) {
if (!head) return head;
quick_sort(head, NULL);
return head;
}
void quick_sort(ListNode *head, ListNode *tail)
{
if (head != tail)
{
// 定义参考元素x,永远取头指针指向的元素
int x = head->val;
// 双指针操作,p之前(不包括head)都是小于x的,p——q(不包括p)都是大于等于x的
// p指针作用: 分段用
// q指针作用: 遍历用,检索当前元素value与x的关系,若value比x小,则扔p前面
ListNode *p = head, *q = p->next;
while (q != tail)
{
if (q->val < x)
{
p = p->next;
swap(p->val, q->val);
}
q = q->next;
}
// 遍历完之后,详情见图片中粉字
// 其实就是把参考元素当分段点放在p所指位置上,p之前全部<x,p之后>=x
if (p != head) swap(head->val, p->val);
quick_sort(head, p);
quick_sort(p->next, tail);
}
}
};
写的很清晰