基于单链表的快速排序算法（C++）_c++实现单链表快速排序

考研倒计时4天，写个代码放松放松。

国科大19年863最后一题数据结构大题：待排序列采用带头结点的单链表，写出在其上进行的快速排序的递归算法。

算法思想：快排核心思想是每一趟确定一个基元素的最终位置，小于它的在左边，大于它的在右边。题目给了单链表，那就没办法随机访问，但是不影响将一段链表分为两段的操作，那就用几个指针通过一次遍历将一段链表分为两段，然后基元素放中间，最后递归左右两段链表就行了。时间复杂度不变的，依然是O(n log n)。

代码如下：

#include <iostream>
using namespace std;
/*
题目：链式存储的快排
作者：伊特玛德神
算法思想：
每一趟以第一个元素为基准
q依次后移，若小于基准，则与p交换
p与q之间的维持大于基准的元素
最后将基准与p交换
此时基准左边是小于的链表，右边是大于的
然后进行下一趟
快排左边和右边的链表
*/
typedef struct node {
	int val;
	node* next;
}node;
 
void my_swap(node* p, node* q) {
	// 自写交换函数
	// 只交换值，不更改链表指针，减少执行时间
    // 这里如果想交换指针，就需要增加前驱，麻烦点而已
	int tmp = p->val;
	p->val = q->val;
	q->val = tmp;
}
 
void quick_sort_list(node* head, node* tail) {
	if (head == tail || head == NULL || head == tail->next