2023年5月26日
先来回顾一下昨天的面试题及答案：
「合并两个有序链表」（Merge Two Sorted Lists）。
题目描述：将两个升序链表合并为一个新的升序链表并返回。新链表应该通过拼接给定的两个链表的节点组成。
例如，给定链表1: 1->2->4，链表2: 1->3->4，将它们合并为新的链表：1->1->2->3->4->4。
以下是对应的JavaScript实现：
function mergeTwoLists(l1, l2) {// 创建一个哑节点作为合并后链表的头节点const dummy = new ListNode(-1);let curr = dummy;// 比较两个链表的节点值，将较小值的节点连接到合并后链表的尾部while (l1 !== null && l2 !== null) {if (l1.val <= l2.val) {curr.next = l1;l1 = l1.next;} else {curr.next = l2;l2 = l2.next;}curr = curr.next;}// 处理其中一个链表已遍历完的情况if (l1 !== null) {curr.next = l1;}if (l2 !== null) {curr.next = l2;}return dummy.next; // 返回合并后链表的头节点
}解题思路：
创建一个哑节点作为合并后链表的头节点，并用一个指针
curr指向当前合并后链表的尾节点。比较两个链表的节点值，将较小值的节点连接到合并后链表的尾部，并将对应链表的指针向后移动。
当其中一个链表已遍历完时，将另一个链表的剩余部分直接连接到合并后链表的尾部。
返回合并后链表的头节点，即哑节点的下一个节点。
时间复杂度：遍历两个链表的所有节点，时间复杂度为 O(m+n)，其中 m 和 n 分别为两个链表的长度。
空间复杂度：只使用了常量级别的额外空间，因此空间复杂度为 O(1)。
例如：
// 构造链表节点
function ListNode(val) {this.val = val;this.next = null;
}// 构造链表
function createLinkedList(arr) {const dummy = new ListNode(-1);let curr = dummy;for (let i = 0; i < arr.length; i++) {curr.next = new ListNode(arr[i]);curr = curr.next;}return dummy.next;
}// 打印链表
function printLinkedList(head) {let curr = head;const result = [];while (curr !== null) {result.push(curr.val);curr = curr.next;}console.log(result.join("->"));
}const l1 = createLinkedList([1, 2, 4]);
const l2 = createLinkedList([1, 3, 4]);const mergedList = mergeTwoLists(l1, l2);
printLinkedList(mergedList); // 1->1->2->3->4->4在上述例子中，给定两个链表 l1 和 l2，分别为 1->2->4 和 1->3->4。通过调用 mergeTwoLists 函数，将两个链表合并为一个新的升序链表。最终得到的合并后链表为 1->1->2->3->4->4。
2023年5月27日
给定 n 个非负整数 a1，a2，...，an，代表坐标中的 n 个点 (i, ai)。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
上面问题的答案会在第二天的公众号推文中公布，大家可以关注公众号：程序员每日三问，第一时间获得推送内容。
学习不打烊，充电加油只为遇到更好的自己,每天早上9点纯手工发布面试题（死磕自己，愉悦大家） 希望大家在这浮夸的程序员圈里保持冷静，每天坚持花20分钟来学习与思考，在千变万化，类库层出不穷的今天，不要等到找工作时才狂刷题，提倡每日学习。
