问题：已知一个有序循环链表，插入一个结点值为num的结点，使循环链表依然有序。
解法：
如果链表为空
1.直接插入。
如果链表不为空
1.声明两个指针型结点型变量p1，p2，p1指向首结点，p2指向首结点下一个结点。
2.若待插入值num >= p1->val 并且 num<= p2->val，即插入p1与p2之间。若不符合，p1与p2依次往后移动继续比较。
3.如果p2循环到head仍没有合适位置插入的话，此时num的值有两种情况：
插入值比头结点的值小 或者 插入值比尾结点的值大。这影响了插入值最终插入head之后（插入值比头结点的值小）还是插入head之前（插入值比尾结点的值大）。（本题使用的是head->val=NULL,head->next为首节点的结构）
以下附上代码，包括尾插法建立循环链表函数initListEnd()，以及解决本题的插入函数insertNum()：
#include<iostream>
#include<cstdlib>
using namespace std;
struct LNODE
{
int val;
LNODE *pnext;
};
LNODE* initListEnd(int arr[],int n) //尾插法建立循环链表，head:目标链表头结点，arr[]:插入值存放数组，n:数组长度
{
LNODE *head = (LNODE*)malloc(sizeof(LNODE));
head->pnext = NULL;
LNODE *tmpNode; //临时结点用来存放当前arr的值
LNODE *endNode; //始终指向目标链表尾端的节点
endNode = head; //此时目标链表只有头结点
for(int i = 0 ; i < n ; ++i ) //将arr[]中的值依次依次插入链表尾端
{
tmpNode = (LNODE*)malloc(sizeof(LNODE)); //为新结点申请空间
tmpNode->val = arr[i]; //新结点赋值
endNode->pnext = tmpNode; //目标链表尾指向新结点
endNode = endNode->pnext; //更新endNode使其指向目标结点尾端
}
endNode->pnext = head; //构建循环链表
return head;
}
void insertNum(LNODE *head,int num) //head待插入有序循环链表，num带插入值
{
LNODE *numNode = (LNODE*)malloc(sizeof(LNODE));
numNode->val = num;
if(head->pnext == NULL)//如果head为空，直接插入并构造循环链表
{
head->pnext = numNode;
numNode->pnext = head;
return ;
}
else//head不为空
{
LNODE *p1,*p2;
p1 = head->pnext;
p2 = head->pnext->pnext;
int flag = 1;//flag用来记录是否在p2循环到头结点之前就已经找到合适的插入位置
//flag为1表示遍历整个链表后没有找到合适位置，需要进行下一步比较
while(flag && p2!=head)
{
if(num >= p1->val && num<= p2->val)//成功插入链表中间
{
p1->pnext = numNode;
numNode->pnext = p2;
flag = 0;
break;
}
p1 = p1->pnext;
p2 = p2->pnext;
}
if(flag)//没有插入链表中间，进行下一步比较，确定num插入head之前，还是head之后。
{
if(p1->val <= num)
{
p1->pnext = numNode;
numNode->pnext = p2;
}
else
{
p2 = head->pnext;
head->pnext = numNode;
numNode->pnext = p2;
}
}
}
}
int main()
{
int n = 5;
int arr[n]={1,3,5,7,9};
LNODE *head;
head = initListEnd(arr,n);//尾插法创建循环链表
cout<<"插入前："<<endl;
LNODE *tNode = head->pnext; //创建临时结点tNode依次输出链表各结点的值
while(tNode->pnext != head)
{
cout<<tNode->val<<" "<<endl;
tNode = tNode->pnext;
}
cout<<tNode->val<<endl; //最后一个结点pnext已经为NULL了，所以循环中没有输出它，需要单独输出
insertNum(head,0);//向有序循环链表中插入值并保证依然有序
cout<<"插入后："<<endl;
tNode = head->pnext; //创建临时结点tNode依次输出链表各结点的值
while(tNode->pnext != head)
{
cout<<tNode->val<<" "<<endl;
tNode = tNode->pnext;
}
cout<<tNode->val<<endl; //最后一个结点pnext已经为NULL了，所以循环中没有输出它，需要单独输出
return 0;
}
