【问题描述】输入n个整数，创建一个双向循环链表进行存储。这些整数从第二个开始，递增有序（设a2<a3<...<an） (ai为第i个整数)。试编写程序，创建双向循环链表，依次将输入的整数存储在该链表的各节点中。然后，将第一个结点删除并插入链表中的适当位置，使整个链表递增有序。
【输入形式】先输入整数的个数，再输入整数列。
【输出形式】以整数递增的顺序，依次输出双向循环链表各个节点存储的整数。
【样例输入】5 3 1 2 4 5
【样例输出】1 2 3 4 5
【样例说明】输入数据的第一个数是整数的个数，其后是整数列，该整数列从第二个开始，递增有序，数据间以空格分开。
【评分标准】根据输入的数据创建双向循环链表，并把原来部分有序的链表处理成有序的链表并输出。
我猜是这么实现,可能和别的地方不太一样
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,flag=0;
typedef struct Node
{
int x;
Node *next;
Node *pre;
}Node;
int main()
{
scanf("%d",&n);
Node *fir=(Node*)malloc(sizeof(Node));
Node *head=(Node*)malloc(sizeof(Node));
head->next=fir;
head->pre=fir;
fir->next=NULL;
fir->pre=head;
scanf("%d",&fir->x);
Node *p;
for(int i=2;i<n;i++)
{
p=(Node*)malloc(sizeof(Node));
scanf("%d",&p->x);
p->pre=head->next;
(head->next)->next=p;
head->next=p;
p->next=NULL;
}
p=(Node*)malloc(sizeof(Node));
scanf("%d",&p->x);
p->pre=head->next;
(head->next)->next=p;
head->next=p;
p->next=head->pre;
int j=2;
if((fir->x)<((fir->next)->x))
{
flag=1;
}
if(!flag)
{
for(Node *i=fir->next;;i=i->next)
{
if((fir->x)<((i->next)->x))
{
head->pre=fir->next;
fir->next=i->next;
fir->pre=i;
i->next=fir;
(i->next)->pre=fir;
break;
}
if(j==n-1)
{
if((fir->x)>=((i->next)->x))
{
head->pre=fir->next;
fir->next=head->pre;
fir->pre=i->next;
(i->next)->next=fir;
}
break;
}
j++;
}
}
j=1;
for(Node *i=head->pre;;i=i->next)
{
printf("%d ",i->x);
if(j==n) break;
j++;
}
return 0;
}
原文：https://www.cnblogs.com/reashal/p/14692249.html