程序员代码面试指南 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++版的题解。

全部评论
这个解法是错误的,虽然可以成功提交,这是因为这道题测试用例太差了。 如果你运行下面的测试用例,你会得出错误的结果: 2 1 3 0 你的代码的运行结果为:1 0 3 , 显然结果错误,正确结果应该为 0 1 3 问题在于你的代码没有考虑比头节点还要小的情况。从链表的尾结点开始遍历,可以解决这种情况。
点赞 回复 分享
发布于 2022-05-23 12:05

相关推荐

07-20 21:57
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务