程序员代码面试指南 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;
}
程序员代码面试指南（C++版题解） 文章被收录于专栏
主要是为左程云的《程序员代码面试指南》这本书改写C++版的题解。
