当前位置：首页 > news >正文

HOT100DAY2记录用

news 2026/3/27 5:49:05

继续学习链表

一.解题记录

21.合并两个有序链表

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

方法：迭代

class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 创建一个虚拟头节点（哨兵节点），值为-1（这个值不重要） // 它的作用是为了避免处理头节点为空的特殊情况 ListNode prehead = new ListNode(-1); // cur指针指向当前已经合并好的链表的最后一个节点 // 初始时指向虚拟头节点 ListNode cur = prehead; // 同时遍历两个链表，直到其中一个链表遍历完 while (l1 != null && l2 != null) { // 比较两个链表当前节点的值 if (l1.val <= l2.val) { // 如果l1的值小于等于l2，将l1接到合并链表后面 cur.next = l1; // l1指针向后移动一位 l1 = l1.next; } else { // 如果l2的值小于l1，将l2接到合并链表后面 cur.next = l2; // l2指针向后移动一位 l2 = l2.next; } // cur指针也向后移动一位，指向新加入的节点 cur = cur.next; } // 当循环结束时，说明其中一个链表已经遍历完了 // 将另一个链表剩余的部分直接接到合并链表的末尾 // 这里使用了三元运算符：如果l1为空，就接l2，否则接l1 cur.next = l1 == null ? l2 : l1; // 返回虚拟头节点的下一个节点，即真正的头节点 // 这样就跳过了我们创建的虚拟节点 return prehead.next; } }

时间复杂度与空间复杂度：

时间复杂度：O(m + n)，其中 m 和 n 分别是两个链表的长度
空间复杂度：O(1)，只使用了常数额外空间（虚拟头节点不计入，因为它是输出的一部分）

70.爬楼梯

假设你正在爬楼梯。需要n阶你才能到达楼顶。

每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

public int climbStairs(int n) { // 基础情况处理：n=0,1,2 时直接返回结果 // 爬到第0阶（起点）视为1种方法 if (n == 0) { return 1; } // 爬到第1阶：只有1种方法（1步） else if (n == 1) { return 1; } // 爬到第2阶：有2种方法（1+1 或 2） if (n == 2) { return 2; } // n >= 3 时，使用滚动数组计算 else { // twoStepsAgo: f(n-2)，即爬到第 n-2 阶的方法数 // oneStepAgo: f(n-1)，即爬到第 n-1 阶的方法数 // current: f(n)，即爬到第 n 阶的方法数 int twoStepsAgo = 1; // 初始对应 f(1) = 1 int oneStepAgo = 1; // 初始对应 f(2) 的前一个状态，实际是 f(1) = 1 int current = 2; // 初始对应 f(2) = 2 // 从第3阶开始迭代计算到第n阶 for (int i = 3; i <= n; i++) { // 滚动更新：f(n-2) ← f(n-1) twoStepsAgo = oneStepAgo; // f(n-1) ← f(n) oneStepAgo = current; // f(n) = f(n-1) + f(n-2) current = twoStepsAgo + oneStepAgo; } return current; } }

时间复杂度	O(n)	循环从 i=3 执行到 i=n，共执行 n-2 次，与输入规模 n 成线性关系
空间复杂度	O(1)	使用固定数量的变量（twoStepsAgo、oneStepAgo、current），不随 n 增大而增加

448.找到所有数组中消失的数字

给你一个含n个整数的数组nums，其中nums[i]在区间[1, n]内。请你找出所有在[1, n]范围内但没有出现在nums中的数字，并以数组的形式返回结果。

思路：建一个长度为len+1的桶，每个桶用于对应数字计数，然后输出所有为0的桶

class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { int lens = nums.length; int[] box = new int[lens + 1]; // 计数数组，下标从1开始 List<Integer> result = new ArrayList<>(); // 存储结果的列表 // 统计每个数字出现的次数 for (int i = 0; i < lens; i++) { box[nums[i]]++; } // 找出没出现的数字 for (int i = 1; i <= lens; i++) { if (box[i] == 0) { result.add(i); // 将缺失的数字加入结果列表 } } return result; } }

时间复杂度	O(n)	两个独立循环，每个循环执行 n 次，总执行次数约 2n
空间复杂度	O(n)	使用了长度为 n+1 的额外数组 box