前些天去华赛面试，在经过详细的面试后，考官最后让我写一个链表排序的小程序，居然还写错了，惭愧回来痛定思痛，重新再实现了一遍
template<typename T>
struct list_node
{
struct list_node<T> *next;
T value;
};
template<typename T>
struct _list
{
struct list_node<T> *head;
int size;
};
template<typename T>
void SortLink(struct _list<T> * link) {
struct list_node<T> *pHead,*pRear,*p,*tp;
if (!link) return;
for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {
for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)
if (pHead->value>=p->value)
tp->next=p->next,p->next=pHead,pHead=p,p=tp;
if (!pRear) link->head=pHead;
else pRear->next=pHead;
pRear=pHead;
}
}
template<typename T>
void InsertSort(struct _list<T> * list) {
struct list_node<T> *pHead,*p,*tp,*m,*n;
if (!list) return;
pHead=list->head;
p=pHead->next;
while(!p)
{
tp=p;
p=p->next;
for(m=NULL;n=pHead;n!=NULL &&tp->next>n->value;m=n,n=n->next);
if(!m)
pHead=tp;
else
{
m->next=tp;
}
tp->next=n;
}
}
template <typename T>
void ReverseList(struct _list<T> * link)
{
struct list_node<T> *pHead,*pRear,*p,*tp;
pHead=link->head;
p=pHead->next;
pHead->next=NULL;
for(;p;p=tp)
{
tp=p->next;
p->next=pHead;
pHead=p;
}
link->head=pHead;
};