带头结点的单链表L，设计一个算法使其元素递增 -006

带头结点的单链表L，设计一个算法使其元素递增

总结

​ 先构成只含一个数据结点的有序单链表，然后以此扫描单链表中剩下的结点p（直至p==NULL为止），在有序表中通过比较查找插入P的前驱结点pre，然后将p插入到pre之后。

代码

#include <iostream>
using namespace std;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

void Sort(LinkList &L){
    LNode *p=L->next,*pre;   //p，pre分别作为两个链表的工作指针
    LNode *r=p->next;      //r为p的后继结点，保证不断链
    p->next=NULL;         //构造只含有一个数据结点的有序表
    p=r;                //使得p作为单链表的工作指针
    while(p!=NULL){
        r=p->next;        //将r后移防止断链
        pre=L;          //每次循环，保证pre指向头结点，方便从头开始比较大小
        while(pre->next!=NULL&&pre->next->data<p->data){    //比较大小，直到满足，才在pre后面插入p结点
            pre=pre->next;
        }
        p->next=pre->next;   //插入的通用算法
        pre->next=p;
        p=r;
    }
}