Question

C++中怎么对链表进行插入式排序？

例如：链表中插入数据的同时进行排序，用指针怎么做？
英文名叫insert sort linked list

Answer 1

#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

struct node
{
int item;
node *next;
node(int x, node* t)
{
item = x;
next = t;
}
};

typedef node *link;

link reverse(link x)
{
link t, y=x, r=0;
while(y!=0)
{
t = y->next;
y->next = r;
r = y;
y = t;
}
return r;
}

static const int N = 100;

int main()
{
node heada(0, 0);
link pa = &heada, walkera = pa;
for(int i=0; i<N; i++) //生成随机链表序列
{
walkera = (walkera->next = new node(rand() % 1000, 0));
}

node headb(0, 0);
link pb=&headb, walkerb, x;
//根结点b指向链表a中的节点，不需要重新生成结点
for(walkera = pa->next; walkera != 0; walkera = x) //遍历链表a
{
x = walkera->next;
for(walkerb=pb; walkerb->next !=0; walkerb=walkerb->next) //遍历链表b
if(walkerb->next->item > walkera->item) break; //下一个结点的值比要插入的结点的值大就跳出
walkera->next = walkerb->next;
walkerb->next = walkera;
}

walkerb = pb;
while(walkerb->next != 0)
{
cout << setw(5) << walkerb->item;
walkerb = walkerb->next;
}

return 0;
}