思路和**一样，可能代码看上去有点照抄嫌疑，但是根据我的思考过程写的~ 望**勿怪，水平有限，大家多指正。
#include <iostream>
#include <stdio.h>
using namespace std;
struct st
{
int a;
st(int i){ a = i; }
struct st* next;
};
void sort(struct st* &head)
{
st* p = 0;//排序后的链表头
st* p1 = head;//排序前的链表头
st* p2 = p1;//在排序过程中，保存原始链表头
for(;p2;)
{
p2 = p1->next;
p1->next = p;
//以上2步，是将当前节点从链表中取出然后将指针反向指向
p = p1;//将排序好的链表的头，给p
p1 = p2;//将p1重新指向链表的首位置
}
head = p;//让head重新指向排序好的链表头
}
void print(struct st* p)
{
for(;p;)
{
cout << p->a << endl;
p = p->next;
}
}
int main( void )
{
st* head = new st(0);
st* p = head;
p->next = new st(1);
p = p->next;
p->next = new st(2);
p = p->next;
p->next = new st(3);
p = p->next;
p->next = 0;
print(head);
sort(head);
cout << "----------------------" << endl;
print(head);
return 0;
}
//20070126=====================
可能这么说更好理解点：
实际上可以看作是2个list.,从原始list的head开始逐个取节点，然后向目的list的头的位置插入。
sort的循环中，前2句为取，后2句为插。