AcWing 1451. 单链表快速排序
原题链接
简单
作者:
qing123
,
2021-09-28 14:25:34
,
所有人可见
,
阅读 299
采用交换的方法
C++ 代码
class Solution {
public:
ListNode* quickSortList(ListNode* head) {
if(!head) return head; //空表情况的判断
quickSort(head, NULL); //进行快速排序
return head;
}
//使用交换元素值
void quickSort(ListNode* head, ListNode* tail) //后一个参数是尾指针
{
if (head != tail) //没有走到尾部
{
int key = head->val; //去表头值作为关键字
ListNode *p = head, *q = p->next; //q作为遍历指针进行遍历
while(q != tail) { //q遍历完所以的点
if(q->val < key) { //通过尾插法插入到q的后面去,
p = p->next; //小于key的数+1,并且将该数当到p的尾部,
swap(p->val, q->val);
}
q = q->next;
}
if(p != head) //有小于key的元素
swap(head->val, p->val);//轴枢放在中间去
quickSort(head, p); //排前半部分,和后半段,递归求解子问题
quickSort(p->next, tail);
}
}
};