大厂面试必看！Java单链表排序的2种方法，附完整代码与优化思路

游戏天地 2025年09月05日 11:39 1 admin

在互联网大厂的软件开发面试中，数据结构与算法是绕不开的 “硬骨头”，而单链表排序更是高频考点。无论是字节跳动的校招笔试，还是阿里的技术一面，都曾多次出现 “用 Java 实现单链表排序” 的题目。很多面试者虽然知道排序算法的基本思想，但一到链表场景就容易卡壳 —— 毕竟链表没有数组的随机访问特性，指针操作稍有不慎就会出现环或者空指针异常。今天，我们就深入剖析单链表排序的两种核心实现：归并排序和插入排序，从原理拆解到 Java 代码落地，再到面试高频问题解析，帮你彻底拿下这个考点。

先搞懂面试题的 “隐藏要求”：单链表排序的核心难点

在动手写代码前，我们必须先明确单链表排序和数组排序的本质区别，这也是大厂面试官考察的重点。数组排序可以通过下标直接访问元素，而单链表只能通过next指针遍历，这就带来了三个核心难点：

无法随机访问中间元素：像数组的快速排序需要频繁取中间元素作为基准，在链表中实现会非常低效；

指针操作易出错：合并、分割链表时，若指针指向混乱，容易出现链表断裂、环结构等问题；

空间复杂度限制：面试中常要求 “原地排序”（即额外空间复杂度尽可能低），这对算法选择提出了更高要求。

针对这些难点，归并排序（时间复杂度 O (nlogn)）和插入排序（空间复杂度 O (1)）成为最适合单链表的两种算法 —— 前者满足大厂对效率的要求，后者符合 “原地排序” 的场景需求。接下来我们逐一拆解，并附上完整的 Java 实现。

归并排序：单链表的 “效率之王”，Java 实现与细节优化

归并排序的核心思想是 “分治”：将链表拆分成多个子链表，分别排序后再合并。这种思路天然适配链表，因为拆分和合并过程都可以通过指针操作高效完成，且时间复杂度稳定在 O (nlogn)，是大厂面试中最推荐的单链表排序方法。

1. 归并排序的 “三步走” 思路（链表版）

与数组归并排序不同，链表的归并排序不需要额外开辟空间存储子数组，而是通过指针调整实现拆分与合并，具体分为三步：

拆分（Divide）：用 “快慢指针” 找到链表的中间节点，将链表分成左右两个子链表；
递归排序（Conquer）：递归地对左右两个子链表执行归并排序，直到子链表只有一个节点（天然有序）；
合并（Merge）：将两个已排序的子链表合并成一个有序链表，通过比较节点值调整指针指向。

2. Java 完整实现：从节点定义到核心方法

首先，我们需要定义单链表的节点类 —— 这是所有操作的基础，面试时务必手写正确：

// 单链表节点定义class ListNode {    int val;    ListNode next;    // 构造方法    ListNode(int val) {        this.val = val;        this.next = null;    }    // 用于测试：根据数组创建链表    public static ListNode createList(int[] arr) {        if (arr == null || arr.length == 0) return null;        ListNode head = new ListNode(arr[0]);        ListNode cur = head;        for (int i = 1; i < arr.length; i++) {            cur.next = new ListNode(arr[i]);            cur = cur.next;        }        return head;    }    // 用于测试：打印链表    public static void printList(ListNode head) {        ListNode cur = head;        while (cur != null) {            System.out.print(cur.val + " -> ");            cur = cur.next;        }        System.out.println("null");    }}

接下来实现归并排序的核心逻辑，分为 “拆分” 和 “合并” 两个子方法：

（1）拆分：找中间节点，分割链表

利用 “快慢指针”（快指针一次走 2 步，慢指针一次走 1 步）找到链表的中间节点，然后将慢指针的next置为null，实现链表分割。这里要注意边界条件：当链表为空或只有一个节点时，无需拆分。

// 拆分链表：返回中间节点的下一个节点（右链表的头）private static ListNode split(ListNode head) {    if (head == null || head.next == null) return null;    ListNode slow = head; // 慢指针：最终指向左链表的尾    ListNode fast = head.next; // 快指针：从next开始，确保拆分均匀    // 快指针走到末尾时，慢指针在中间    while (fast != null && fast.next != null) {        slow = slow.next;        fast = fast.next.next;    }    ListNode rightHead = slow.next;    slow.next = null; // 分割左、右链表    return rightHead;}

（2）合并：将两个有序链表合并

合并过程类似 “合并两个有序链表” 的经典题：创建一个虚拟头节点，依次比较两个链表的节点值，将较小的节点连接到虚拟头节点后，最后返回合并后的头节点。

// 合并两个有序链表private static ListNode merge(ListNode left, ListNode right) {    ListNode dummy = new ListNode(-1); // 虚拟头节点，简化边界处理    ListNode cur = dummy;    // 同时遍历两个链表，比较并连接节点    while (left != null && right != null) {        if (left.val <= right.val) {            cur.next = left;            left = left.next;        } else {            cur.next = right;            right = right.next;        }        cur = cur.next;    }    // 连接剩余的节点（若有）    cur.next = (left != null) ? left : right;    return dummy.next; // 返回合并后的头节点（跳过虚拟节点）}

（3）主方法：递归执行归并排序

// 归并排序主方法public static ListNode mergeSort(ListNode head) {    // 递归终止条件：链表为空或只有一个节点    if (head == null || head.next == null) return head;    // 1. 拆分：获取右链表的头节点    ListNode rightHead = split(head);    // 2. 递归排序左、右链表    ListNode leftSorted = mergeSort(head);    ListNode rightSorted = mergeSort(rightHead);    // 3. 合并两个有序链表    return merge(leftSorted, rightSorted);}

3. 测试与面试细节优化

我们用一个测试案例验证效果：对链表4 -> 2 -> 1 -> 3进行排序：

public static void main(String[] args) {    int[] arr = {4, 2, 1, 3};    ListNode head = ListNode.createList(arr);    System.out.println("排序前：");    ListNode.printList(head); // 输出：4 -> 2 -> 1 -> 3 -> null        ListNode sortedHead = mergeSort(head);    System.out.println("排序后：");    ListNode.printList(sortedHead); // 输出：1 -> 2 -> 3 -> 4 -> null}

面试时，面试官可能会追问 “如何优化空间复杂度？”—— 默认的递归实现空间复杂度为 O (logn)（递归调用栈），若要实现 O (1) 空间复杂度，可将递归改为迭代版归并排序（非递归），核心思路是 “从子链表长度 1 开始，逐步合并相邻的子链表”，这里给出关键逻辑：

// 迭代版归并排序（空间复杂度O(1)）public static ListNode mergeSortIterative(ListNode head) {    if (head == null) return null;    int length = getLength(head); // 计算链表长度    ListNode dummy = new ListNode(-1);    dummy.next = head;        // 子链表长度从1开始，每次翻倍    for (int step = 1; step < length; step *= 2) {        ListNode prev = dummy;        ListNode curr = dummy.next;        // 按step分割并合并        while (curr != null) {            ListNode left = curr;            ListNode right = splitByStep(left, step); // 按步长拆分            curr = splitByStep(right, step); // 下一组的头            prev.next = merge(left, right); // 合并当前组            // 移动prev到合并后的尾            while (prev.next != null) {                prev = prev.next;            }        }    }    return dummy.next;}// 按步长拆分链表private static ListNode splitByStep(ListNode head, int step) {    if (head == null) return null;    ListNode cur = head;    // 走step-1步，找到拆分点    for (int i = 1; i < step && cur.next != null; i++) {        cur = cur.next;    }    ListNode next = cur.next;    cur.next = null;    return next;}// 计算链表长度private static int getLength(ListNode head) {    int len = 0;    while (head != null) {        len++;        head = head.next;    }    return len;}

迭代版避免了递归调用栈的开销，空间复杂度降至 O (1)，更能体现你的技术深度，面试时主动提出会加分不少。

插入排序：原地排序的 “性价比之选”，Java 实现与边界处理

插入排序的核心思想是 “逐步构建有序序列”：将链表分为 “已排序” 和 “未排序” 两部分，每次从末排序部分取一个节点，插入到已排序部分的合适位置。虽然时间复杂度为 O (n²)，但空间复杂度仅为 O (1)，适合链表长度较短的场景，也是面试中常考的 “原地排序” 实现。

1. 插入排序的链表适配思路

与数组插入排序不同，链表的插入不需要移动元素，只需调整指针，具体步骤如下：

创建一个虚拟头节点，作为已排序部分的 “哨兵”（简化头节点插入的边界处理）；
遍历未排序链表的每个节点（记为curr）；
在已排序部分中找到curr的插入位置（即找到第一个比curr大的节点的前一个节点prev）；
调整指针：将curr从原位置移除，插入到prev之后；
重复步骤 2-4，直到未排序部分为空。

2. Java 完整实现与边界处理

// 单链表插入排序public static ListNode insertionSort(ListNode head) {    // 边界条件：空链表或只有一个节点，直接返回    if (head == null || head.next == null) return head;        ListNode dummy = new ListNode(-1); // 已排序部分的虚拟头    ListNode curr = head; // 未排序部分的当前节点        while (curr != null) {        // 1. 保存curr的下一个节点（避免插入后丢失后续节点）        ListNode next = curr.next;                // 2. 在已排序部分找到插入位置：prev的next大于curr.val        ListNode prev = dummy;        while (prev.next != null && prev.next.val < curr.val) {            prev = prev.next;        }                // 3. 插入curr到prev之后        curr.next = prev.next; //  curr指向prev的原next        prev.next = curr; //  prev指向curr                // 4. 移动到下一个未排序节点        curr = next;    }        return dummy.next; // 返回已排序链表的头}

同样用测试案例验证：对链表-1 -> 5 -> 3 -> 4 -> 0排序：

面试高频问题：归并排序 vs 插入排序，怎么选？

大厂面试官常会问：“什么时候用归并排序，什么时候用插入排序？” 这里给出清晰的判断标准，帮你从容应答：

对比维度	归并排序（链表版）	插入排序（链表版）
时间复杂度	O (nlogn)（稳定高效）	O (n²)（适合短链表）
空间复杂度	递归版 O (logn)，迭代版 O (1)	O (1)（原地排序）
适用场景	链表长度较长、对效率要求高	链表长度短、内存资源紧张
稳定性	稳定（相等元素相对位置不变）	稳定