最近在网上冲浪的时候，我发现了一个有意思的讨论：互联网公司里为啥很少有山东大学呢？这个问题我有点好奇万能的网友们会怎么说，于是进去看了看，没想到网友回答出奇一致。

帖子里，有个网友表示，几家公司了，但他竟然一个山大的学生都没遇见过。我仔细想了下，似乎真的很少听说山东大学出身的互联网从业者。

不过，一个人的社交圈有限，能接触到的同事和行业内的人也就那么多，你没看到，不代表没有。但是网友们的回答却出奇的一致：山东大学的大部分去考公了。



通过网友的回复，可以看到这种趋势确实存在。但也有网友回答有很多啊，可能只是你没碰到。


所以，互联网行业并不是没有山东大学的从业者。只不过，相比之下比较少。

下面是今日大厂算法题


今日算法题，来自LeetCode的第21题：合并两个有序链表，下面是我的算法思路及实现，让我们来看看吧。

算法题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

算法思路

创建一个哑节点：这个哑节点将作为结果链表的起始节点，这样可以简化边界条件的处理，最后返回它的下一个节点作为合并后的链表头。
迭代比较：比较两个链表当前节点的值，将较小值的节点接在结果链表的后面，并移动该链表的指针到下一个节点。
连接剩余部分：如果两个链表的长度不同，将较长链表的剩余部分直接接在结果链表的后面。
返回结果：返回哑节点的下一个节点，即合并后链表的头节点。
代码实现

C语言实现
#include <stdlib.h>
struct ListNode {    int val;    struct ListNode *next;};
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {    struct ListNode dummy;    struct ListNode *tail = &dummy;    dummy.next = NULL;
    while (l1 && l2) {        if (l1->val < l2->val) {            tail->next = l1;            l1 = l1->next;        } else {            tail->next = l2;            l2 = l2->next;        }        tail = tail->next;    }
    tail->next = l1 ? l1 : l2;    return dummy.next;}

Java实现
public class ListNode {    int val;    ListNode next;    ListNode() {}    ListNode(int val) { this.val = val; }    ListNode(int val, ListNode next) { this.val = val; this.next = next; }}
public class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        ListNode dummy = new ListNode(-1);        ListNode tail = dummy;
        while (l1 != null && l2 != null) {            if (l1.val < l2.val) {                tail.next = l1;                l1 = l1.next;            } else {                tail.next = l2;                l2 = l2.next;            }            tail = tail.next;        }
        tail.next = l1 != null ? l1 : l2;        return dummy.next;    }}
‍

Python实现
class ListNode:    def __init__(self, val=0, next=None):        self.val = val        self.next = next
def merge_two_lists(l1, l2):    dummy = ListNode()    tail = dummy
    while l1 and l2:        if l1.val < l2.val:            tail.next = l1            l1 = l1.next        else:            tail.next = l2            l2 = l2.next        tail = tail.next
    tail.next = l1 if l1 else l2    return dummy.next

算法解析

这个算法的时间复杂度是O(n+m)，其中n和m分别是两个链表的长度。这是因为我们只需要一次遍历就能完成合并。空间复杂度是O(1)，我们只需要常数空间存储几个指针。

示例和测试

假设有两个链表 l1: 1->2->4 和 l2: 1->3->4，合并后的链表是 1->1->2->3->4->4。

总结

合并两个有序链表是一个非常基础且实用的链表操作问题，它不仅能帮助我们熟悉链表的基本操作，还能训练我们使用指针进行有效的链表操作。

扫描下方二维码，购买《AI实战课程》，送ChatGPT独享账号！


推荐阅读：
Suno v3发布：5秒即可生成2分钟的高音质歌曲
马斯克脑机接口公司Neuralink直播首位人类受试者近况
某员工爆料，跳槽PDD，薪资涨幅真不错！每天十点回家，周六加班拼老命。。。