Java链表合并与降序排序方法

本文深入剖析了Java中链表合并与降序排序的典型陷阱与正确解法，重点揭示了字符串误用导致的“10

本文详解如何将两个用户输入的整数序列构建为有序链表，合并后按数值大小降序排列——关键在于将输入字符串正确解析为整数再比较，避免按字典序排序导致 10 < 1 的逻辑错误。

本文详解如何将两个用户输入的整数序列构建为有序链表，合并后按数值大小降序排列——关键在于将输入字符串正确解析为整数再比较，避免按字典序排序导致 10 < 1 的逻辑错误。

在 Java 中处理用户输入的数字序列时，若直接以字符串形式插入链表并调用 String.compareTo() 进行排序，会触发字典序（lexicographic）比较，而非数值大小比较。例如 "10".compareTo("1") 返回正值（因为 '1' == '1'，但 "10" 更长，而字符串比较中 "1" 实际小于 "10"？不——准确地说："1".compareTo("10") 返回负值，因为比较 '1' vs '1' 相等，接着 ""（空）vs '0' → 空字符串小于任何非空字符串，因此 "1" < "10"；而 "10".compareTo("2") 返回负值（'1' < '2'），导致 10 被错误地排在 2 前面。这正是示例中输出 9 8 4 3 2 10 1 0 的根本原因：10 被当作字符串参与了升序插入（<= 0 判断），最终反转后仍保持错误相对顺序。

要实现真正的数值降序排列，核心改造点有三：

1. 输入解析：将 split(" ") 后的每个 String 显式转换为 int；
2. 数据封装：链表节点应存储 int 类型值，而非 String；
3. 比较逻辑：所有插入、合并中的大小判断均基于 int 数值运算（如 a > b），杜绝字符串比较。

以下是重构后的关键代码（精简可运行版本）：

// Merge.java（重构后）
public class Merge {
    static class Node {
        int data;   // ✅ 改为 int 类型
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;
    private int size;

    // 按数值降序插入（最大值在前）
    public void insert(int value) {
        Node newNode = new Node(value);
        if (head == null || value >= head.data) {
            // 插入头部：保证降序（大→小）
            newNode.next = head;
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null && current.next.data > value) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
        size++;
    }

    // 合并两个已按降序排列的链表（归并思想，O(m+n)）
    public static Merge merge(Merge list1, Merge list2) {
        Merge merged = new Merge();
        Node h1 = list1.head, h2 = list2.head;

        // 归并：始终取当前较大的元素
        while (h1 != null && h2 != null) {
            if (h1.data >= h2.data) {
                merged.insert(h1.data); // ✅ insert 自动维持降序
                h1 = h1.next;
            } else {
                merged.insert(h2.data);
                h2 = h2.next;
            }
        }
        // 处理剩余节点
        while (h1 != null) {
            merged.insert(h1.data);
            h1 = h1.next;
        }
        while (h2 != null) {
            merged.insert(h2.data);
            h2 = h2.next;
        }
        return merged;
    }

    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

在主程序 HOMEWORK.java 的 case 3 中同步更新输入处理逻辑：

case 3:
    Merge list1 = new Merge();
    Merge list2 = new Merge();

    System.out.println("Enter first sequence (space-separated integers):");
    String[] tokens1 = input.nextLine().trim().split("\\s+"); // 防止多余空格
    for (String s : tokens1) {
        if (!s.isEmpty()) {
            list1.insert(Integer.parseInt(s)); // ✅ 字符串转 int
        }
    }

    System.out.println("Enter second sequence:");
    String[] tokens2 = input.nextLine().trim().split("\\s+");
    for (String s : tokens2) {
        if (!s.isEmpty()) {
            list2.insert(Integer.parseInt(s));
        }
    }

    Merge merged = Merge.merge(list1, list2); // ✅ 静态方法更清晰
    System.out.println("Result (descending order):");
    merged.display();
    break;

注意事项与最佳实践：

• ✅ 异常处理：生产代码中应在 Integer.parseInt() 外包裹 try-catch，捕获 NumberFormatException 并提示用户输入格式错误；
• ✅ 空输入防御：使用 trim().split("\\s+") 可鲁棒处理首尾空格及多个空格分隔；
• ⚠️ 性能提示：上述 merge 方法中每次调用 insert() 是 O(n) 操作，整体为 O(n²)。若需最优效率，可先将两链表遍历转为 ArrayList，Collections.sort(list, Collections.reverseOrder())，再构建新链表（O(n log n)）；
• ? 设计解耦：Merge 类目前承担“存储”“排序”“合并”多重职责。更工程化的做法是分离 SortedLinkedList（专注有序维护）与 ListMerger（专注合并算法）。

通过将数据类型从 String 升级为 int，并确保所有比较逻辑基于数值语义，即可彻底解决 10 被误判为小于 1 的问题，输出严格按数学大小降序排列的结果：10 9 8 4 3 2 1 0。

好了，本文到此结束，带大家了解了《Java链表合并与降序排序方法》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！