程序员代码面试指南 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

相关推荐

白火同学:先说结论,准大三不是特别好找实习,boss沟通300+没有实习是很正常的情况。一是暑期实习时间太短了,二是在这么多准大四都找不到实习,从实习时间和掌握技术层面,企业会优先看他们。 再说简历,其实985本+准大三到这水平的简历也很优秀了,要说的话,项目经历可以再优化一下,可以基本围绕采取STAR原则,分为项目概述、技术架构、技术亮点、实现结果,再发给AI润色一下。 最后说操作,准大三的话,如果想找实习那就多投,不过现在也7月中旬了,时间上已经略晚了。如果7月底实在找不到,也可以多刷点算法,多学点技术,这实习也不至于一定得有,当然有更好。
点赞 评论 收藏
分享
写不来代码的小黑:这么小的城市能有做it的公司也不容易
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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