程序员代码面试指南 2.18：向有序的环形单链表中插入新节点

1、思路

• 遍历有序环形链表，找到小于num的节点；

• 创建num节点，将它插入到合适的位置即可；

• 考虑到待插入节点的值可能比头节点更小的情况，要从链表的尾结点开始遍历。若遍历了一圈没有找到小于num的节点，则在表尾后（即表头前）新增这个num节点。

2、代码

list_node * insert_num(list_node * head, int num)
{
    auto p = head;
    while (p->next != head) p = p->next;    //找到尾结点
    
    auto tail = p;
    while (p->next != tail && p->next->val < num)
    {
        p = p->next;                        //从尾节点开始找到小于num的节点
    }
    
    list_node *newNode = new list_node();   //创建新节点
    newNode->val = num;
  
    newNode->next = p->next;                //插入到p与p->next之间
    p->next = newNode;
    
    return head;
}