（线性表）已知一双向循环链表，从第二个结点至表尾递增有序，（设a1<x<an）如下图(“第二个结点至表尾”指a1…an )。试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序。

（线性表）已知一双向循环链表，从第二个结点至表尾递增有序，（设a1<x<an）如下图(“第二个结点至表尾”指a1…an )。试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序。

思路：先让第一个结点tmp脱离链表，然后遍历脱离后的链表找到第一个大于tmp的结点，让tmp插入到它前面，如果都没有大于它的就插入到头结点前面。
代码：下面给出了链表从建立到删除第一个结点并插入到合适位置的所有代码。其中的bool ChangeLinkList(nodeList &L)函数为你需要的核心代码。

//构建结点结构体
typedef struct Node {
    int data;
    Node* next;//后驱
    Node* pre;//前驱
}*nodeList;
void InitLinkList(nodeList &L) {
    //初始化链表，建立头结点
    L= new Node();
    L->next = NULL;
}
bool CreateLinkList(nodeList &L) {
    //创建链表
    int n;
    cin >> n;//scanf("%d",n);C语言用这个
    //进行尾插法
    if (n <= 0)
        return false;
    Node*rear = L;//尾指针，指向链表的尾部
    for (int i = 0; i < n; i++) {
        Node* p = new Node();
        cin >> p->data;//scanf("%d",p->data);C语言用这个
        rear->next = p;
        p->pre = rear;
        rear = p;
    }
    rear->next = L;
    L->pre = rear;
    return true;
}
void printfList(nodeList &L) {
    //用来打印链表，验证是否为正序
    Node*p = L->next;
    while (p!=L) {
        cout << p->data << " ";//printf("%d ",p->data);C语言用这个
        p = p->next;
    }
    cout << endl;//printf("\n");C语言用这个
}
bool ChangeLinkList(nodeList &L) {
    //将第一个结点删除并插入表中适当位置，使整个链表递增有序
    if (!L->next)//一个结点也没有
        return false;
    Node*tmp = L->next;//存放第一个结点
    //让第一个结点脱离链表
    L->next = tmp->next;
    tmp->next->pre = L;
    //找到链表中第一个大于tmp的结点p
    Node*p = L->next;
    while (p->data < tmp->data&&p->next!=L) {
        p = p->next;
    }
    if (p->data < tmp->data)//说明链表中所有结点都小于tmp
        p = L;
    //让tmp插入到p->pre和p之间
    Node*p_pre = p->pre;
    p_pre->next = tmp;
    p->pre = tmp;
    tmp->pre = p_pre;
    tmp->next = p;
    return true;
}
int main() {
    Node*L = NULL;
    InitLinkList(L);
    CreateLinkList(L);
    printfList(L);
    ChangeLinkList(L);
    printfList(L);
}