【抖音面经】不愧是字节系|0814

• 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；以此类推，直到最高位。在排序过程中，相同元素在各个位上的值也相同，因此它们的相对顺序在排序过程中不会改变，所以基数排序也是稳定的。

10. 合并两个有序链表？

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个哨兵节点，方便处理边界情况
        ListNode dummy = new ListNode(0);
        // 初始化一个指针，用于构建合并后的链表
        ListNode current = dummy;

        // 当两个链表都不为空时，进行合并
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                // 将l1的当前节点连接到结果链表上
                current.next = l1;
                l1 = l1.next; // 移动l1的指针
            } else {
                // 将l2的当前节点连接到结果链表上
                current.next = l2;
                l2 = l2.next; // 移动l2的指针
            }
            // 移动结果链表的指针
            current = current.next;
        }

        // 如果l1还有剩余节点，直接连接到结果链表末尾
        if (l1 != null) {
            current.next = l1;
        }
        // 如果l2还有剩余节点，直接连接到结果链表末尾
        if (l2 != null) {
            current.next = l2;
        }

        // 返回合并后的链表的头节点（哨兵节点的下一个节点）
        return dummy.next;
    }
}

首先创建了一个哨兵节点（dummy node），来简化边界条件的处理。

使用一个循环来遍历两个链表，并根据当前节点的值将较小的节点连接到结果链表的末尾。

当其中一个链表遍历完成后，将另一个链表的剩余部分直接连接到结果链表的末尾。

最后，我们返回哨兵节点的下一个节点作为合并后链表的头节点。

面经原帖由牛客609584840号发布，答案由程序员Hasity整理。