DarkYellowCat's Blog

分享技术与思考

0%

发表于 分类于
目录
前言
常用方法
基础运算符
高频位运算技巧
判断相同/不同字符的个数
拼接 + 判断一个数是否为2的幂

前言

力扣最近几天的每日一题基本都与位运算有关，让本就没有专门训练的鄙人在“模拟 -> 超时/报错”的循环中有些裂开。于是决定重学位运算，并将自己遇到的一些套路整合一下。

常用方法

bitCount(int n)

接收一个整数n，返回n的二进制中有多少个1

底层 Brian Kernighan 算法

1
2
3
4
5
6
int count = 0;
while (n != 0) {
    n = n & (n - 1);
    count++;

}

每执行一次 n & (n-1)，都会消掉最低位的一个 1。

基础运算符

与 &

两个位都为 1 才是 1
用途：

  • 判断某一位是否为 1
  • 判断是否为 2 的幂
  • 清除最低位的 1
    例：
1
n & 1    // 判断奇偶

或 |

有一个为 1 就是 1
用途：

  • 置某一位为 1
  • 拼接二进制

非 ~

按位取反

Java 是补码表示

1
~x = -x - 1

异或 ^

不同为 1，相同为 0

核心性质：
a ^ a = 0
a ^ 0 = a
满足交换律和结合律

用途：

  • 找只出现一次的数
  • 交换两个数
  • 判断不同位

高频位运算技巧

1. 判断奇偶

1
(n & 1) == 0  // 偶数

2. 取最低位的 1

1
lowbit = n & (-n);

例：

1
2
3
n = 12 = 1100  
-n = 0100  
结果 = 0100

用途：

  • 树状数组
  • 快速拆分二进制

3. 删除最低位的 1

1
n = n & (n - 1);

4. 判断第 k 位是否为 1

1
((n >> k) & 1) == 1

5. 设置第 k 位为 1

1
n = n | (1 << k);

6. 清除第 k 位

1
n = n & ~(1 << k);

7. 切换第 k 位

1
n = n ^ (1 << k);

判断相同/不同字符的个数

用一个整数作为 26 位 bitmask。

例如：

1
2
3
4
int mask = 0;
for (char c : s.toCharArray()) {
    mask ^= (1 << (c - 'a'));
}

用途：

  • 判断是否出现奇数次
  • 回文排列问题

拼接 + 判断一个数是否为2的幂

拼接

左移 + 或

1
result = (result << shift) | x;

a << b将 a 的二进制表示向左移动 b 位，
相当于乘以 2^b，
在右边补 0

两个二进制数对应位有 1 则结果为 1，
相当于将两个数的二进制位合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int A = 6;  // 二进制: 110
int B = 5;  // 二进制: 101

// 获取 B 的二进制长度
int lenB = Integer.toBinaryString(B).length();  // lenB = 3

// 方法1：使用数学公式
int result1 = A * (int)Math.pow(2, lenB) + B;  // 6 * 8 + 5 = 53

// 方法2：使用位运算
int result2 = (A << lenB) | B;  // (110 << 3) | 101 = 110000 | 101 = 110101

System.out.println("A: " + Integer.toBinaryString(A));      // 110
System.out.println("B: " + Integer.toBinaryString(B));      // 101
System.out.println("拼接结果: " + Integer.toBinaryString(result2));  // 110101
System.out.println("十进制: " + result2);  // 53

判断一个数是否为2的幂

逻辑:

2的幂的二进制表示只有一个1，其余都是0：按位与（&）的结果是0

  • 1 = 0001
  • 2 = 0010
  • 4 = 0100
  • 8 = 1000

示例：

1
2
3
n      = 8  = 1000  (二进制)
n - 1  = 7  = 0111
n & (n-1) = 1000 & 0111 = 0000 = 0

对应题目

连续连接二进制字符串数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    private static final int MOD = 1000000007;

    public int concatenatedBinary(int n) {
        long result = 0;
        int shift = 0;  // 移位数
        for (int i = 1; i <= n; i++) {
            // 判断一个数是否为2的幂
            if ((i & (i - 1)) == 0) {
                shift++;
            }
            result = ((result << shift) | i) % MOD;
        }
        return (int) result;
    }
}

发表于

更新规划

docker学习笔记

计算机网络

发表于 更新于 分类于

背景

在将项目升级到 Spring Boot 3.2.x + Java 17 后，项目在启动阶段直接退出，没有
Exception in thread "main" 或 Caused by，导致问题难以定位。

最初怀疑过：

  • Knife4j / Swagger
  • Hutool 工具类
  • 枚举定义
  • 配置文件错误

但检查后发现都不是原因。

报错信息

开启 DEBUG 日志后，启动过程中出现如下关键信息：

1
2
3
4
5
Creating MapperFactoryBean with name 'userMapper'
...
Exception encountered during context initialization - cancelling refresh attempt:
java.lang.IllegalArgumentException:
Invalid value type for attribute 'factoryBeanObjectType': java.lang.String

随后 Spring 容器初始化被中断，程序直接退出。

这个异常没有堆栈向下追踪信息。

排查过程

1. 确认异常类型

程序属于：

  • 启动阶段直接退出（exit）
  • 而不是卡死或运行时报错

说明问题发生在 Spring 容器初始化早期阶段。

2. 锁定异常位置

从日志可以确认异常发生在：

1
MapperFactoryBean 创建阶段

并且与 MyBatis Mapper 扫描 直接相关。

3. 检查依赖树

执行命令：

1
mvn dependency:tree | findstr mybatis

输出如下：

1
2
com.baomidou:mybatis-plus-boot-starter:3.5.9
└── org.mybatis:mybatis-spring:2.1.2

这里发现了一个关键问题：

mybatis-spring 2.1.2 是为 Spring 5 设计的

而 Spring Boot 3 使用的是 Spring Framework 6

4. 问题本质

Spring Framework 6 对 FactoryBean 的类型推断规则进行了严格校验：

  • 不再接受 String 类型的 factoryBeanObjectType
  • 必须是 Class<?>

而 mybatis-spring 2.x 内部仍使用旧方式注册 Bean 元数据，导致 Spring 6 直接抛出：

1
Invalid value type for attribute 'factoryBeanObjectType'

由于这是 容器元数据校验失败，并非运行期异常，因此不会有常见的 Caused by 堆栈。

解决方案

1. 排除不兼容的 mybatis-spring

在 mybatis-plus-boot-starter 中排除旧依赖：

1
2
3
4
5
6
7
8
9
10
11
<dependency>
    <groupId>com.baomidou</groupId>
    <artifactId>mybatis-plus-boot-starter</artifactId>
    <version>3.5.9</version>
    <exclusions>
        <exclusion>
            <groupId>org.mybatis</groupId>
            <artifactId>mybatis-spring</artifactId>
        </exclusion>
    </exclusions>
</dependency>

2. 手动引入 Spring 6 兼容版本

1
2
3
4
5
<dependency>
    <groupId>org.mybatis</groupId>
    <artifactId>mybatis-spring</artifactId>
    <version>3.0.3</version>
</dependency>

3. 清理并重新构建

1
mvn clean

然后在 IDEA 中重新刷新 Maven 依赖。

4. 验证修复结果

再次执行：

1
mvn dependency:tree | findstr mybatis-spring

确认只存在：

1
org.mybatis:mybatis-spring:3.0.3

项目即可正常启动。

总结

这次问题的几个特点：

  • 无 Caused by
  • 无 main 线程异常
  • 代码本身正确
  • 只在 Spring Boot 3 + MyBatis 组合下触发
  • 依赖版本与 Spring 6 不兼容

(注)虽然感觉可能性不大，但旧的依赖可能是MyBatis-Plus自己引入的。但因为无法百分百确定自己当初有没有引入，所以不能实锤。

发表于 更新于 分类于

需知：

  • 本文提到的模板均为Java实现;
  • 主要为基础算法和数据结构(滑动窗口、01背包等)，不会出现较为复杂的类型(线段树、替罪羊树);
  • 会提及对应的知识点，但主要集中于模板，不适合完全不了解的读者；
  • 题目来源于leetcode。
目录
前缀和与差分
滑动窗口
单调栈
回溯
DFS与BFS
01背包与完全背包
杂项

前缀和与差分

前缀和

思想

用空间换时间
将原始数据进行预处理，构建新数组，其中每个位置存储从起点到当前位置的和。

1
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

利用前缀和数组快速计算任意区间和 : 

1
sum[left, right] = prefix[right+1] - prefix[left]

模板

一维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Main{
    // 求区间[x,y]之和
    public int PrefixSum1D(int[] nums, int x, int y){
        int n = nums.length;

        // 构建前缀和数组
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        return query(prefix ,x, y);
    }
    // 查询区间[left, right]的和
    public int query(int[] prefix, int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

二维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main {
    // 求二维数组从 (row1, col1) 到 (row2, col2) 的元素之和
    public int PrefixSum2D(int[][] matrix, int row1, int col1, int row2, int col2) {
        int m = matrix.length, n = matrix[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefix[i + 1][j + 1] = matrix[i][j]
                        + prefix[i][j + 1]
                        + prefix[i + 1][j]
                        - prefix[i][j];
            }
        }
        return query(prefix, row1, col1, row2, col2);
    }
    // 通过前缀和数组查询指定区域的元素之和
    public int query(int[][] prefix ,int row1, int col1, int row2, int col2) {
        return prefix[row2 + 1][col2 + 1]
                - prefix[row1][col2 + 1]
                - prefix[row2 + 1][col1]
                + prefix[row1][col1];
    }
}
  • 注：二维数组会产生重合部分，在计算时要减去 𝑆3,3=𝐴3,3+𝑆2,3+𝑆3,2−𝑆2,2 (设S为前缀和数组，A为原数组)

适用范围

  1. 频繁查询区间和
  2. 统计满足条件的子数组/子矩阵
  3. 滑动窗口优化
  4. 数据预处理后多次查询

例题

209 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

差分

思想

差分是前缀和的逆运算，核心思想是：将对区间的多次修改操作，转化为对差分数组的两次单点修改，最后通过一次前缀和得到最终结果。

预处理

1
2
diff[i] = a[i] - a[i-1]  (i ≥ 1)
diff[0] = a[0]

区间修改（对 a[l..r]加上 val）：

1
2
diff[l] += val
diff[r+1] -= val

二维

1
2
3
4
5
6
7
diff[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

子矩阵修改 对(x1,y1)到(x2,y2)加上val
diff[x1][y1] += val
diff[x2+1][y1] -= val
diff[x1][y2+1] -= val
diff[x2+1][y2+1] += val

模板

1
2
3
4
5
6
7
8
9
10
11
12
public class Main {
    // 求数组的差分数组
    public int[] Diff(int[] nums) {
        int n = nums.length;
        int[] diff = new int[n];
        diff[0] = nums[0];
        for (int i = 0; i < n; i++) {
            diff[i] = diff[i + 1] - nums[i];
        }
        return diff;
    }
}

适用范围

  1. 频繁进行区间修改，最后查询结果
  2. 对数组/矩阵的多个区间加减操作
  3. 批量更新后求最终状态
  4. 优化多次区间修改的时间复杂度

例题

1109 航班预订统计
这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

滑动窗口

思想

滑动窗口本质是一种双指针 + 区间维护的技巧，用来处理连续子数组 / 子串问题。

通过维护一个 [left, right) 或 [left, right] 的窗口，使区间随着指针移动而“滑动”，避免重复计算。

核心思想：

  • 每个元素最多进窗口一次、出窗口一次

定长窗口

窗口大小 k 固定，只需要关注窗口每次向右移动一格。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    // 在长度为 k 的所有子数组中，求最大和
    public int fixedWindow(int[] nums, int k) {
        int n = nums.length;
        int sum = 0;

        // 初始化第一个窗口
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int ans = sum;

        // 窗口滑动
        for (int i = k; i < n; i++) {
            sum += nums[i];
            sum -= nums[i - k];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

适用范围

  1. 子数组长度固定
  2. 连续区间统计最大值 / 最小值 / 和
  3. 平均值、区间计数类问题

例题

1456.定长字串中元音的最大数目
给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

不定长滑动窗口

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    // 求和 >= target 的最短子数组长度
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0, sum = 0;
        int ans = Integer.MAX_VALUE;

        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

适用范围

  1. 连续子数组 / 子串
  2. 满足某种约束（和、字符种类数等）
  3. 最短 / 最长 区间问题

例题

904.水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

单调栈

思想

单调栈用于维护栈内元素单调递增或递减，常用于解决：

  • 下一个更大元素
  • 上一个更小元素
  • 区间贡献问题

核心特性：

  • 每个元素最多入栈一次、出栈一次
  • 时间复杂度 O(n)

模板 (单调递减栈)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    // 返回每个元素右侧第一个更大的元素
    public int[] nextGreater(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                int idx = stack.pop();
                res[idx] = nums[i];
            }
            stack.push(i);
        }
        return res;
    }
}

适用范围

  1. 下一个 / 上一个更大或更小元素
  2. 直方图最大矩形
  3. 子数组最值贡献计算

例题

215.数组中的第k个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

回溯

思想

回溯是一种暴力枚举 + 剪枝的搜索方式，常用于组合、排列、子集等问题。
核心框架：

  • 做选择
  • 递归
  • 撤销选择

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 求一个数组的所有子集  
class Solution {  
    List<List<Integer>> res = new ArrayList<>();  
    List<Integer> path = new ArrayList<>();  
  
    public List<List<Integer>> subsets(int[] nums) {  
        backtrack(nums, 0);  
        return res;  
    }     
    // 回溯算法  
    private void backtrack(int[] nums, int start) {  
        res.add(new ArrayList<>(path));  
  
        for (int i = start; i < nums.length; i++) {  
            path.add(nums[i]);  
            backtrack(nums, i + 1);  
            path.remove(path.size() - 1);  
        }  
    }  
}

适用范围

  • 全排列 / 组合 / 子集
  • 搜索所有可行解
  • 结果规模指数级

例题

46.全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

DFS与BFS

思想

DFS 和 BFS 是图 / 树搜索的两种基本方式。

DFS：一路走到底（递归 / 栈）

BFS：一层一层扩展（队列）

模板

DFS

1
2
3
4
5
6
7
8
void dfs(int node) {
    visited[node] = true;
    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bfs(int start) {
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int cur = queue.poll();
        for (int next : graph[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

适用范围

  1. 图、树遍历
  2. 连通性问题
  3. 最短路径（无权图）

例题

200.岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

01背包与完全背包

思想

用于在容量限制下选取物品。

  • 01 背包：每个物品只能选一次
  • 完全背包：每个物品可以无限选

模板

01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int knapsack01(int[] w, int[] v, int bag) {
        int n = w.length;
        int[] dp = new int[bag + 1];

        for (int i = 0; i < n; i++) {
            for (int j = bag; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        return dp[bag];
    }
}

完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int completeKnapsack(int[] w, int[] v, int bag) {
        int n = w.length;
        int[] dp = new int[bag + 1];

        for (int i = 0; i < n; i++) {
            for (int j = w[i]; j <= bag; j++) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        return dp[bag];
    }
}

适用范围

  1. 资源有限的最优选择问题
  2. 子集和、零钱兑换
  3. 计数 / 最大值 DP

例题

322.零钱兑换 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

杂项

二进制数字构建

1
val = (val << 1) | root.val;

1. val << 1

  • <<是左移运算符
  • val << 1表示将 val的二进制表示向左移动1位
  • 效果相当于：val * 2
  • 二进制意义：在二进制末尾添加一个0

2. | root.val

  • |是按位或运算符
  • root.val通常是0或1（表示二叉树节点的值）
  • 效果：将移位后的最低位设置为 root.val

3. 整体效果

在已有的二进制数末尾添加一位新数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1 -> 0 -> 1

val = 0

// 第一个节点: root.val = 1
val = (0 << 1) | 1
    = 0 | 1
    = 1   // 二进制: 1

// 第二个节点: root.val = 0
val = (1 << 1) | 0
    = 2 | 0
    = 2   // 二进制: 10

// 第三个节点: root.val = 1
val = (2 << 1) | 1
    = 4 | 1
    = 5   // 二进制: 101

例题

从根到叶的二进制数之和
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。

发表于 更新于 分类于

前言

在练习了一些二叉树的题目后，发现二叉树由于其自身的结构特点，很多题目都可以递归解决。

于是我想，如果你没有掌握二叉树结构或递归思想，可以通过这个章节来进行理解，提高。

我在这里搜集了一些相关的题目，分享思路并给出递归解法(部分题解法不唯一，仅供参考)。

题目主要来源：力扣

二叉树结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode() {};
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

基础

这里讲述一下二叉树和递归的基础概念，供忘了或还没有学的朋友大致了解。

二叉树

二叉树是树结构的一种情况。其中每个节点最多只有两个子节点，分别称为左子树和右子树。

在算法题中，二叉树通常具备以下特点：

  • 结构具有明显的递归性（子树本身仍然是二叉树）

  • 许多问题可以通过“当前节点 + 左右子树”的方式进行拆分

常见的二叉树问题包括遍历、深度/高度计算、结构变换以及基于二叉搜索树性质的判断等。

递归

递归是一种算法思想。其核心在于：将一个问题拆分为若干个规模更小但形式相同的子问题。

有一个非常经典的递归问题：汉诺塔–将n个盘子的移动问题拆解为n-1个盘子的相同问题。

概念：

在一根柱子上从下往上按照大小顺序摞着64个圆盘。把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

代码：

1
2
3
4
5
6
7
8
9
10
11
class HanoiTower{
    public void move(int n, char from, char to, char aux){
        if (n == 1){
            System.out.println("Move disk 1 from " + from + " to " + to);
            return;
        }
        move(n-1, from, aux, to);
        System.out.println("Move disk " + n + " from " + from + " to " + to);
        move(n-1, aux, to, from);
    }
}

方法论

  1. 分析题目是否可以递归完成 (重点看根和左右子树的关系)。
  2. 若可以递归完成，则分析根与左右子树的关系。
  3. 分别取左子树和右子树，这时左右子树又会成为两个根，而这两个根又有自己的左右子树。这样就形成了递归，由根和左右子树的关系去层层递推。
  4. 思考边界条件和返回值。

示例

题目：验证二叉树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 严格小于 当前节点的数。
  • 节点的右子树只包含 严格大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
  1. 通过阅读题目，可以发现：我们先判断根和左右子树，当左子树比根小，右子树比根大，则这一层符合条件。
  2. 可以根据这一判断逻辑进行衍生–当左子树的左子树比左子树小，左子树右子树比左子树大，则这一层符合条件，以此类推
  3. 边界条件：当节点值超出区间时，直接返回 false。空节点视为合法，作为递归的边界条件。
  4. 返回值：返回当前节点是否有效。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root.left == null && root.right == null) return true;
        
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode root, long min, long max) {
        if (root == null) return true;
        if (root.val <= min || root.val >= max) return false;
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}

练习题目

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }
    private void inorder(TreeNode node, List<Integer> res){
        if (node == null){
            return;
        }
        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right, res);
    }
}

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        else if (root.left == null && root.right == null) return 1;
        else {
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }
}

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)   return null;
        TreeNode l = invertTree(root.left);
        TreeNode r = invertTree(root.right);
        root.left = r;
        root.right = l;
        return root;
    }
}

给你一个二叉树的根节点 root ， 检查它是否轴对称。

alt text

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }

    private boolean check(TreeNode p, TreeNode q){
        if(p == null && q == null)    return true;
        if(p == null || q == null)    return false;
        return p.val == q.val && check(p.left,q.right) && check(p.right, q.left);
    }
}

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode node){
        if(node == null){
            return -1;
        }
        int l = dfs(node.left) + 1;
        int r = dfs(node.right) + 1;
        ans = Math.max(l + r, ans);
        return Math.max(l,r);
    }
}

发表于 更新于 分类于

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode() {};
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

1.自顶向下

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        else if (root.left == null && root.right == null) return 1;
        else {
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

2.自底向上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
    int ans = 0;

    private void dfs(TreeNode root, int depth){
        if (root == null) return;
        depth++;
        if (root.left == null && root.right == null){
            ans = Math.max(ans, depth);
        }
        dfs(root.left, depth);
        dfs(root.right, depth);
    }

    public int maxDepth(TreeNode root) {
        dfs(root, 0);
        return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

发表于 更新于 分类于

以中序遍历进行介绍

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode() {};
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

1.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Recursion {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }
    private void preorder(TreeNode node, List<Integer> res){
        if (node == null){
            return;
        }
        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right, res);
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

2.迭代

用栈来实现二叉树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Iteration {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            // 一路向左
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            // 弹出栈顶（最左节点）
            curr = stack.pop();
            ans.add(curr.val);      // 访问
            curr = curr.right;      // 转向右子树
        }
        return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

3.Mirris

对于当前节点 curr：

  • 如果 没有左子树：直接访问 curr，然后进入右子树。
  • 如果 有左子树：
    找到 curr 的前驱节点（即左子树中的最右节点，记为 pre）。
    • 如果 pre.right == null：说明第一次访问，建立线索 pre.right = curr，然后进入左子树。
    • 如果 pre.right == curr：说明左子树已遍历完，断开线索（恢复原树结构），访问 curr，然后进入右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Mirris {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) {
                ans.add(curr.val);
                curr = curr.right;
            } else {
                // 找到左子树的最右节点（前驱）
                TreeNode pre = curr.left;
                while (pre.right != null && pre.right != curr) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    // 建立线索
                    pre.right = curr;
                    curr = curr.left;
                } else {
                    // 线索已存在，说明左子树已遍历完
                    pre.right = null; // 恢复树结构
                    ans.add(curr.val);
                    curr = curr.right;
                }
            }
        }
        return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

4.测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        Recursion recursion = new Recursion();
        List<Integer> res1 = recursion.inorderTraversal(root);
        System.out.println("Recursion: " + res1);

        Iteration iteration = new Iteration();
        List<Integer> res2 = iteration.inorderTraversal(root);
        System.out.println("Iteration: " + res2);

        Mirris mirris = new Mirris();
        List<Integer> res3 = mirris.inorderTraversal(root);
        System.out.println("Mirris: " + res3);
    }
}

给出的树结构：

1
2
3
4
5
1
 \
  2
 /
3

中序遍历（左 → 根 → 右）：[1, 3, 2]

发表于 更新于 分类于

简介

oi-wiki 中对单调队列的解释是：「单调」指的是队列中元素具有某种单调性（递增或递减），而「队列」指元素只能在队头和队尾进行操作。

单调队列并不是一种新的数据结构，而是一种维护队列内部元素有序性的思想。它通常配合滑动窗口问题使用，用于在均摊 O(1) 的时间复杂度内维护区间最值。

常见形式包括：

  • 单调递增队列：队头元素最小
  • 单调递减队列：队头元素最大

Java实现

以下以「维护区间最大值的单调递减队列」为例进行说明。

实现要点：

  1. 队列中存储的是数组下标而不是元素值，便于判断是否滑出窗口
  2. 新元素入队时，从队尾删除所有比它小的元素，维持单调性
  3. 队头若已经不在当前窗口范围内，需要及时弹出

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Deque;
import java.util.ArrayDeque;

public class MonotonicQueue {
    private Deque<Integer> deque = new ArrayDeque<>();

    // 入队：维护单调递减
    public void push(int[] nums, int index) {
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[index]) {
            deque.pollLast();
        }
        deque.offerLast(index);
    }

    // 出队：移除滑出窗口的元素
    public void pop(int indexLimit) {
        if (!deque.isEmpty() && deque.peekFirst() < indexLimit) {
            deque.pollFirst();
        }
    }

    // 获取当前窗口最大值
    public int max(int[] nums) {
        return nums[deque.peekFirst()];
    }
}

例题

给出一个长度为 n 的数组，编程输出每 k 个连续的数中的最大值和最小值。

该问题是单调队列的经典应用，也被称为「滑动窗口最值问题」。

思路说明：

  • 使用一个单调递减队列维护最大值
  • 使用一个单调递增队列维护最小值
  • 窗口每向右移动一步，只需对新元素入队、对过期元素出队即可

示例实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

public class SlidingWindowMinMax {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        Deque<Integer> maxQ = new ArrayDeque<>();
        Deque<Integer> minQ = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            // 维护最大值队列（递减）
            while (!maxQ.isEmpty() && nums[maxQ.peekLast()] <= nums[i]) {
                maxQ.pollLast();
            }
            maxQ.offerLast(i);

            // 维护最小值队列（递增）
            while (!minQ.isEmpty() && nums[minQ.peekLast()] >= nums[i]) {
                minQ.pollLast();
            }
            minQ.offerLast(i);

            // 移除滑出窗口的元素
            if (maxQ.peekFirst() <= i - k) maxQ.pollFirst();
            if (minQ.peekFirst() <= i - k) minQ.pollFirst();

            // 从第一个完整窗口开始输出结果
            if (i >= k - 1) {
                System.out.println(
                    "max=" + nums[maxQ.peekFirst()] + ", min=" + nums[minQ.peekFirst()]
                );
            }
        }
    }
}

时间复杂度分析：

  • 每个元素最多入队、出队一次
  • 总时间复杂度为 O(n)
  • 空间复杂度为 O(k)

该题展示了单调队列在处理区间最值问题时，相比朴素枚举 O(nk) 解法的巨大优势。

发表于 更新于 分类于

本文总结 Java 8 中最常用、最核心的三项特性：Lambda 表达式、Stream API 与 Optional。内容以“已学过、快速回顾与查阅”为目标，侧重概念理解与典型用法。

目录导航

1.Lambda表达式

1.简介

Lambda 表达式是 Java 8 引入的一种匿名函数语法，用于简化只有一个抽象方法的接口（函数式接口）的实现方式。它本质上是一段可以被传递和执行的代码，使 Java 在一定程度上具备了函数式编程的特征。

在 Java 8 之前，若要实现接口通常需要使用匿名内部类，代码冗长且可读性较差。Lambda 表达式通过更简洁的语法，使“做什么”比“怎么写”更加直观。

2.作用

Lambda 表达式的主要作用包括：

  1. 简化代码结构
    使用 Lambda 可以显著减少匿名内部类的样板代码，使核心逻辑更加突出。

  2. 提高可读性
    在集合操作、事件回调等场景中，Lambda 能让代码更加贴近自然语言描述。

  3. 支持函数式编程风格
    Lambda 是 Stream API、Optional 等特性的基础，使 Java 能以声明式方式处理数据。

3.使用

Stream 的典型使用流程为：

  1. 获取 Stream
  2. 中间操作（可选，可多次）
  3. 终止操作

示例：

1
2
3
4
5
6
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);

int sum = list.stream()
        .filter(x -> x % 2 == 0)
        .map(x -> x * x)
        .reduce(0, Integer::sum);

常见中间操作：

  • filter
  • map
  • sorted
  • distinct

常见终止操作：

  • forEach
  • collect
  • reduce
  • count

需要注意：

  • Stream 只能被消费一次
  • Stream 操作是惰性执行的，只有遇到终止操作才会真正执行

4.示例

将传统集合遍历方式改写为 Stream 写法：

1
2
3
4
5
6
7
8
List<String> names = Arrays.asList("Tom", "Jerry", "Alice", "Bob");
List<String> result = new ArrayList<>();

for (String name : names) {
    if (name.length() > 3) {
        result.add(name.toUpperCase());
    }
}

使用 Stream 改写后：

1
2
3
4
List<String> result = names.stream()
        .filter(name -> name.length() > 3)
        .map(String::toUpperCase)
        .collect(Collectors.toList());

Stream 写法将“过滤—转换—收集”的数据处理流程清晰地表达出来，避免了显式的循环和临时变量。

返回顶部

2.Stream API

1.简介

Stream API 是 Java 8 提供的一套用于操作集合数据的全新抽象。Stream 并不是数据结构，而是一种对数据源（如集合、数组）的高层次操作视图。

Stream 强调“做什么”，而非“如何遍历”，通过链式调用的方式完成对数据的处理。

2.作用

Stream API 的主要作用包括：

  1. 简化集合操作
    过滤、映射、排序、聚合等操作可以用一行链式代码完成。

  2. 提高代码表达力
    使用 Stream 可以清晰表达数据处理流程，减少中间变量。

  3. 支持并行处理
    通过 parallelStream()，可以较低成本地利用多核 CPU 提升性能。

3.使用

Stream 的典型使用流程为：

  1. 获取 Stream
  2. 中间操作（可选，可多次）
  3. 终止操作

示例：

1
2
3
4
5
6
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);

int sum = list.stream()
        .filter(x -> x % 2 == 0)
        .map(x -> x * x)
        .reduce(0, Integer::sum);

常见中间操作：

  • filter
  • map
  • sorted
  • distinct

常见终止操作：

  • forEach
  • collect
  • reduce
  • count

需要注意：

  • Stream 只能被消费一次
  • Stream 操作是惰性执行的，只有遇到终止操作才会真正执行

返回顶部

3.Optional

1.简介

Optional 是 Java 8 引入的一个容器类，用于显式表示“可能为空”的值。它的出现旨在减少空指针异常（NullPointerException），并引导开发者以更加安全的方式处理空值。

Optional 本身并不是为了解决所有 null 问题，而是作为一种 API 设计层面的约束和提示。

2.作用

Optional 的主要作用包括：

  1. 减少空指针异常
    通过强制检查或处理空值，降低运行时错误风险。

  2. 提高代码可读性
    方法返回 Optional，可以明确告诉调用者：返回值可能不存在。

  3. 鼓励函数式写法
    Optional 与 Lambda 配合使用，可避免大量的 if-null 判断。

3.使用

创建 Optional 的常见方式：

1
2
3
Optional<String> op1 = Optional.of("Java");
Optional<String> op2 = Optional.ofNullable(null);
Optional<String> op3 = Optional.empty();

常用方法示例：

  1. 判断是否有值
1
op1.isPresent();
  1. 获取值（不推荐直接使用）
1
op1.get();
  1. 提供默认值
1
String s = op2.orElse("default");
  1. 使用 Lambda 处理
1
op1.ifPresent(v -> System.out.println(v));

4.示例

将传统的空值判断代码改写为 Optional 写法：

1
2
3
4
String value = getValue();
if (value != null) {
    System.out.println(value.length());
}

使用 Optional 改写后：

1
2
3
Optional.ofNullable(getValue())
        .map(String::length)
        .ifPresent(System.out::println);

Optional 通过链式调用，将空值判断与业务逻辑合并，使代码更加紧凑且不易出错。

返回顶部

发表于 更新于 分类于

总目录

  1. 链表的中间节点
  2. 反转链表
  3. 回文链表
  4. 重排链表
  5. 移除链表元素
  6. 两两交换链表中的节点
  7. 合并两个有序链表

链表的中间节点-快慢指针

题号：876
给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

输入：head = [1,2,3,4,5]

输出：[3,4,5]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        while(q != null && q.next != null){
            p = p.next;
            q = q.next.next;
        }
        return p;
    }
}
  • 当快指针遍历完时，慢指针刚好在整个链表中间。

反转链表

题号：206

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]

输出：[5,4,3,2,1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode q = head;
        while(q != null){
            ListNode nxt = q.next;
            q.next = pre;
            pre = q;
            q = nxt;
        }
        return pre;
    }
}

回文链表

-前置 ：链表的中间节点、反转链表
题号：234

给你一个单链表的头节点 head，请判断该链表是否为回文链表。

  1. 用快慢指针找到链表中点（偶数长度时取后半段起点，即第二个中间节点）；
  2. 反转后半段链表；
  3. 用两个指针分别从头节点和反转后的后半段头节点同步遍历比较；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean isPalindrome(ListNode head) {
        // 快慢指针
        ListNode fast =head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 反转
        ListNode pre = null;
        ListNode cur = slow;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }

        while (pre != null){
            if(pre.val != head.val){
                return false;
            }
            head = head.next;
            pre = pre.next;
        }
        return true;
    }
}

类似例题

题号：9 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0 || x > 0 && x % 10 == 0){
            return false;
        }
        int rev = 0;
        while(rev < x / 10){
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev == x || rev == x / 10;
    }
}

重排链表

题号：143

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public void reorderList(ListNode head) {
        ListNode mid = middle(head);
        ListNode head2 = reverse(mid);
        while(head2.next != null){
            ListNode nxt = head.next;
            ListNode nxt2 = head2.next;
            head.next = head2;
            head2.next = nxt;
            head = nxt;
            head2 = nxt2;
        }
    }

    private ListNode reverse(ListNode head){
        ListNode pre = null, cur = head;
        while(cur != null){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

    private ListNode middle(ListNode head){
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

移除链表元素

题号：203

输入：head = [1,2,6,3,4,5,6], val = 6

输出：[1,2,3,4,5]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null ){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }
            else{
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

两两交换链表中的节点

题号：24

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

输入：head = [1,2,3,4]

输出：[2,1,4,3]

  • 方法一：迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode node0 = dummy;
        ListNode node1 = head;
        while (node1 != null && node1.next != null) {
            ListNode node2 = node1.next;
            ListNode node3 = node2.next;

            node0.next = node2; // 0 -> 2
            node2.next = node1; // 2 -> 1
            node1.next = node3; // 1 -> 3

            node0 = node1;
            node1 = node3;
        }
        return dummy.next;
    }
}
  • 方法二：递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode node1 = head;
        ListNode node2 = head.next;
        ListNode node3 = node2.next;

        node1.next = swapPairs(node3);
        node2.next = node1;

        return node2;
    }
}

合并两个有序链表

题号：21

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

输入：l1 = [1,2,4], l2 = [1,3,4]

输出：[1,1,2,3,4,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2;
        return dummy.next;
    }
}