单链表的排序

这是前几天hottey面试的一个题目：不借助外部数组，只对链表本身进行操作来完成排序。我觉得甚有意思，便实现了一个。程序代码如下：
#include <iostream>
using namespace std;

template <typename T>
struct node // 节点结构
{
node *next;
T data;
};

template <typename T>
class slist // 单链表结构
{
public:
slist()
{
head.next = NULL;
}
~slist()
{
clear();
}
void clear() // 清空链表
{
node<T> *p;
while (head.next != NULL)
{
p = head.next;
head.next = p->next;
delete p;
}
}
void push_back(T t) // 为简化程序，只提供push_back接口完成元素插入
{
node<T> *p = &head;
while (p->next != NULL)
p = p->next;
node<T> *q = new node<T>;
q->data = t;
q->next = NULL;
p->next = q;
}
void print() // 为简化程序，不提供对operator<<的重载，直接使用成员函数输出
{
node<T> *p;
for (p = head.next; p != NULL; p = p->next)
cout << p->data;
}
void qksort(node<T> *begin, node<T> *end) // 快排
{
if (begin == end) // 递归退出条件
return;
T t;
node<T> *p, *q;
t = begin->data;
q = begin; // q作为哨兵指针
for (p = begin->next; p != end; p = p->next) // 一次快排
{
if (t > p->data)
{
q->data = p->data;
p->data = t;
q = p;
}
}
qksort(begin, q); // 哨兵前的快排
qksort(q->next, end); // 哨兵后的快排
}
void sort() // 调用快排完成排序
{
qksort(head.next, NULL);
}
private:
node<T> head;
};

int main()
{
slist<int> l;
for (int i = 5; i >= 0; i--)
l.push_back(i);
l.print();
cout << endl;
l.sort();
l.print();
return 0;
}

后记：由此亦能看出STL中为list单列一个sort算法的缘由。