基于单链表实现归并排序的技术咨询（附节点定义）

Hey，我来帮你搞定用单链表实现归并排序这件事！先从你给出的节点定义说起，然后一步步拆解实现逻辑～

一、节点定义 #

你给出的Node类已经很基础了，不过我注意到toString方法里多了一个多余的右大括号，我已经帮你修正过来了：

public class Node {
    public int item;
    public Node next;

    public Node(int val) {
        this.item = val;
    }

    public Node() {
    }

    @Override
    public String toString() {
        return "Node{" + "item=" + item + ", next=" + next + '}';
    }
}

二、归并排序的核心原理 #

归并排序是典型的分治算法，针对链表的特性，它的执行流程可以拆解为：

• 拆分阶段：把未排序的链表不断拆分成更小的子链表，直到每个子链表只包含1个元素（单个元素的链表天然是有序的）。
• 合并阶段：反复合并相邻的有序子链表，每次合并后得到新的有序子链表，直到最终合并成一个完整的有序链表。

单链表天生适合归并排序，因为它不需要随机访问元素，正好适配归并排序的“拆分-合并”逻辑，时间复杂度稳定在O(n log n)，空间复杂度主要来自递归调用栈，为O(log n)。

三、具体实现步骤 #

归并排序的实现主要依赖两个核心操作：找到链表中间节点（拆分） 和 合并两个有序链表，再通过递归串联起整个流程。

1. 合并两个有序链表 #

这是归并排序的基础操作，输入两个已经有序的链表，输出一个合并后的有序链表。这里用虚拟头节点来简化边界处理：

private Node merge(Node left, Node right) {
    // 虚拟头节点，避免处理空链表的特殊情况
    Node dummy = new Node();
    Node current = dummy;

    // 逐个比较左右链表的节点，把较小的节点接到结果链表上
    while (left != null && right != null) {
        if (left.item <= right.item) {
            current.next = left;
            left = left.next;
        } else {
            current.next = right;
            right = right.next;
        }
        current = current.next;
    }

    // 把剩余未遍历完的链表节点直接接上去
    if (left != null) {
        current.next = left;
    }
    if (right != null) {
        current.next = right;
    }

    return dummy.next;
}

2. 找到链表的中间节点（拆分链表） #

用快慢指针法来找中间节点：快指针每次走两步，慢指针每次走一步，当快指针走到链表末尾时，慢指针正好指向链表的中间位置，这样就能把链表拆分成左右两部分：

private Node findMiddle(Node head) {
    // 如果链表为空或者只有一个节点，直接返回头节点
    if (head == null || head.next == null) {
        return head;
    }

    Node slow = head;
    Node fast = head.next;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

3. 递归实现归并排序 #

通过递归不断拆分链表，直到每个子链表只有一个节点，然后开始向上合并：

public Node mergeSort(Node head) {
    // 递归终止条件：链表为空或者只有一个节点，无需排序
    if (head == null || head.next == null) {
        return head;
    }

    // 找到中间节点，拆分链表为左右两部分
    Node middle = findMiddle(head);
    Node rightHead = middle.next;
    middle.next = null; // 断开左右链表，避免合并时互相干扰

    // 递归排序左右两个子链表
    Node leftSorted = mergeSort(head);
    Node rightSorted = mergeSort(rightHead);

    // 合并两个有序子链表，返回最终的有序链表头节点
    return merge(leftSorted, rightSorted);
}

四、测试示例 #

你可以用下面的代码来测试实现是否正确：

public static void main(String[] args) {
    // 构建一个未排序的链表：4 -> 2 -> 1 -> 3
    Node head = new Node(4);
    head.next = new Node(2);
    head.next.next = new Node(1);
    head.next.next.next = new Node(3);

    // 执行归并排序
    Node sortedHead = new MergeSortLinkedList().mergeSort(head); // 假设上述方法都在MergeSortLinkedList类中

    // 打印排序后的链表
    Node current = sortedHead;
    while (current != null) {
        System.out.print(current.item + " ");
        current = current.next;
    }
    // 预期输出：1 2 3 4
}

内容的提问来源于stack exchange，提问作者Arefe