问题：已知一个有序循环链表，插入一个结点值为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;
}