2023年大厂前端面试高频算法题：合并有序链表

在2023年的前端求职面试中，算法题作为高频考点，对于理解和解决这类问题至关重要。本篇内容主要关注于合并两个有序链表的问题，这是一个经典的编程题目，常用于考察面试者的数据结构和递归/迭代思维。 题⽬描述： 题目要求将两个已排序的链表合并成一个新的有序链表。例如，给定链表1 -> 2 -> 4 和 1 -> 3 -> 4，合并后的链表应为 1 -> 1 -> 2 -> 3 -> 4 -> 4。这个任务需要候选人具备链表的基本操作和理解，特别是对递归或迭代算法的掌握。 前置知识： - 递归：理解递归函数的概念，如何通过函数调用自身来解决问题，这在处理分治问题时尤其重要。 - 链表：熟悉单链表的数据结构，包括节点的定义（如`ListNode`类），以及链表的常见操作，如访问、插入和删除节点。 思路： 解决此问题可以采用递归方法。首先，比较两个链表头部的值，选择较小的那个节点作为合并后的链表的下一个节点，并递归地对剩余部分进行同样的操作。当其中一个链表为空时，将另一个链表剩余部分直接连接到结果链表上，直到两个链表都遍历完。 关键点： - 链表操作的熟练程度，包括链表节点的创建和链接。 - 理解递归终止条件：当一个链表为空时，停止递归，避免无限循环。 - 边界情况：确保处理空链表和只有一个元素的链表，防止程序出错。 代码实现： - 递归JavaScript代码： ```javascript function mergeTwoLists(l1, l2) { if (l1 === null) { return l2; } if (l2 === null) { return l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } ``` - 迭代C++代码： ```cpp class Solution { public: ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode head, *tail = &head; while (a && b) { if (a->val <= b->val) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = a ? a : b; return head.next; } }; ``` 复杂度分析： - 时间复杂度：O(M+N)，其中M和N分别为两个链表的长度，因为每个节点最多只会被遍历一次。 - 空间复杂度：O(log(min(M, N)))，递归解决方案中，调用栈的最大深度取决于较短链表的长度。 扩展： 题目还提示了迭代的解决方案，使用迭代方法可以避免递归带来的额外空间开销。迭代方式通过设置两个指针分别指向两个链表，同时移动，每次比较节点值并添加到结果链表中，直到遍历完整个链表。迭代版本的时间和空间复杂度与递归版相同，但更直观且避免了递归带来的栈空间消耗。