本文讲解如何利用 Java 标准库中的 LinkedList（而非自定义 ListNode）高效合并两个已排序链表，涵盖数据转换、双指针归并逻辑、注意事项及完整可运行示例。
本文讲解如何利用 java 标准库中的 `linkedlist`（而非自定义 `listnode`）高效合并两个已排序链表，涵盖数据转换、双指针归并逻辑、注意事项及完整可运行示例。
LeetCode 第 21 题“合并两个有序链表”本意是训练对链表指针操作的理解，因此平台预置了 ListNode 类（含 val 和 next 字段）。但如果你希望完全避开手动定义节点、直接使用 Java 内置的 java.util.LinkedList，这是可行的——前提是明确：LinkedList<E> 是双向链表实现，其 API（如 get()、add()、remove()）不暴露底层指针，因此无法直接模拟 list1.next = list2 这类原地链接操作。我们必须采用“数据提取 → 归并 → 构建新链表”的策略，而非原地指针拼接。
✅ 正确思路：转为数组/队列 + 双指针归并
由于 LinkedList 不支持 O(1) 的 next 指针跳转，我们应：
- 将两个 LinkedList<Integer> 视为有序序列；
- 使用两个索引（i, j）模拟“指针”，遍历各自列表；
- 比较当前元素，将较小者添加到结果链表；
- 索引后移，直到任一列表遍历完毕；
- 将剩余元素批量追加。
以下是完整、可运行的解决方案：
import java.util.*;
public class MergeTwoSortedLists {
public static LinkedList<Integer> mergeTwoLists(LinkedList<Integer> l1, LinkedList<Integer> l2) {
LinkedList<Integer> result = new LinkedList<>();
int i = 0, j = 0;
// 双指针归并（O(m+n)）
while (i < l1.size() && j < l2.size()) {
if (l1.get(i) <= l2.get(j)) {
result.add(l1.get(i++));
} else {
result.add(l2.get(j++));
}
}
// 追加剩余元素
while (i < l1.size()) result.add(l1.get(i++));
while (j < l2.size()) result.add(l2.get(j++));
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String line1 = scanner.nextLine().trim();
String line2 = scanner.nextLine().trim();
LinkedList<Integer> list1 = new LinkedList<>();
LinkedList<Integer> list2 = new LinkedList<>();
if (!line1.isEmpty()) {
Arrays.stream(line1.split("\s+"))
.map(String::trim)
.filter(s -> !s.isEmpty())
.map(Integer::parseInt)
.forEach(list1::add);
}
if (!line2.isEmpty()) {
Arrays.stream(line2.split("\s+"))
.map(String::trim)
.filter(s -> !s.isEmpty())
.map(Integer::parseInt)
.forEach(list2::add);
}
// 注意：题目保证输入已排序，故无需再调用 Collections.sort()
LinkedList<Integer> merged = mergeTwoLists(list1, list2);
System.out.println(merged); // 输出格式如: [1, 2, 3, 4, 5]
}
}⚠️ 关键注意事项
- 不要重复排序：题目明确输入为“已排序链表”，代码中 Collections.sort() 是冗余且低效的（O(n log n)），应删除；
- LinkedList.get(i) 时间复杂度为 O(i)：虽整体仍为 O(m+n)，但比原生 ListNode 的 O(1) next 访问慢；若性能敏感，建议回归 ListNode 实现；
- 空输入处理：示例中已通过 trim() 和 filter 健壮处理空行或空格；
- 类型安全：使用 Integer 而非 String 存储数值，避免字符串比较（如 "10" < "2" 错误）；
- LeetCode 的设计意图：平台提供 ListNode 是为了强化基础数据结构与指针思维——掌握 next 操作对后续树、图等题目至关重要。
✅ 总结
使用 java.util.LinkedList 解决该题是合法且可实现的，但本质是将链表当作有序列表处理，依赖索引访问与值比较，而非链式指针操作。它适合初学者快速验证逻辑，但长远来看，理解并手写 ListNode 及其指针操作，才是掌握链表算法的核心路径。
立即学习“Java免费学习笔记（深入）”；
