如何在 Java 中使用内置 LinkedList 类合并两个已排序链表-java教程-PHP中文网

如何在 Java 中使用内置 LinkedList 类合并两个已排序链表

本文讲解如何利用 Java 标准库中的 LinkedList（而非自定义 ListNode）高效合并两个已排序链表，涵盖数据转换、双指针归并逻辑、注意事项及完整可运行示例。

本文讲解如何利用 java 标准库中的 `linkedlist`（而非自定义 `listnode`）高效合并两个已排序链表，涵盖数据转换、双指针归并逻辑、注意事项及完整可运行示例。

LeetCode 第 21 题“合并两个有序链表”本意是训练对链表指针操作的理解，因此平台预置了 ListNode 类（含 val 和 next 字段）。但如果你希望完全避开手动定义节点、直接使用 Java 内置的 java.util.LinkedList，这是可行的——前提是明确：LinkedList 是双向链表实现，其 API（如 get()、add()、remove()）不暴露底层指针，因此无法直接模拟 list1.next = list2 这类原地链接操作。我们必须采用“数据提取 → 归并 → 构建新链表”的策略，而非原地指针拼接。

✅ 正确思路：转为数组/队列 + 双指针归并

由于 LinkedList 不支持 O(1) 的 next 指针跳转，我们应：

Java Maven Code Review

审查Java Maven项目（ZIP压缩包或GitLab仓库URL），检查代码规范、命名、模块边界、可维护性问题以及重复代码。

下载

将两个 LinkedList 视为有序序列；
使用两个索引（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  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]
    }
}</integer></integer></integer></integer></integer></integer>

⚠️ 关键注意事项

不要重复排序：题目明确输入为“已排序链表”，代码中 Collections.sort() 是冗余且低效的（O(n log n)），应删除；
LinkedList.get(i) 时间复杂度为 O(i)：虽整体仍为 O(m+n)，但比原生 ListNode 的 O(1) next 访问慢；若性能敏感，建议回归 ListNode 实现；
空输入处理：示例中已通过 trim() 和 filter 健壮处理空行或空格；
类型安全：使用 Integer 而非 String 存储数值，避免字符串比较（如 "10"
LeetCode 的设计意图：平台提供 ListNode 是为了强化基础数据结构与指针思维——掌握 next 操作对后续树、图等题目至关重要。