#include <bits/stdc++.h>
using namespace std;
struct linklist{
int val;
struct linklist* next;
linklist(int x) : val(x), next(nullptr){};
};
linklist* getPartion(linklist* phead, linklist* pend)
{
int key = phead->val;
linklist* p = phead;
linklist* q = p->next;
while(q != pend)
{
if(q->val < key)
{
p = p->next;
swap(p->val, q->val);
}
q = q->next;
}
swap(p->val, phead->val);
return p;
}
void linklistSort(linklist* listBegin, linklist* listEnd)
{
if(listBegin != listEnd)
{
linklist* node = getPartion(listBegin,listEnd);
linklistSort(listBegin,node);
linklistSort(node->next,listEnd);
}
}
void print_list(linklist* phead)
{
linklist* pNode = phead;
while(pNode != nullptr)
{
cout << pNode->val <<" ";
pNode = pNode->next;
}
}
int main()
{
int arr[] = {1,2,3,0,4,9,5,7};
linklist* pbegin = new linklist(NULL);
linklist* pNode = pbegin;
for (int i : arr) {
auto* node = new linklist(i);
pNode->next = node;
pNode = pNode->next;
}
print_list(pbegin->next);
cout << endl;
linklistSort(pbegin->next,nullptr);
print_list(pbegin->next);
return 0;
}