每日算法 — 使用java实现链表排序：归并排序与链表指针操作

问题引入

链表是数据结构的基础构件，但对链表进行高效排序却不像数组那样直观——无法随机访问，不能直接用快速排序的分区操作。本文聚焦链表的归并排序实现，从快慢指针找中点、递归分治到有序链表合并，完整讲解如何用Java在 O(n log n) 时间、O(1) 额外空间（自底向上版本）内完成链表排序。

算法原理

为什么选归并排序

归并排序天然适合链表：合并两个有序链表只需调整指针，无需额外数组空间。

核心步骤

1. 找中点：快慢指针法。fast 每次走两步，slow 每次走一步，当 fast 到达末尾时，slow 即为中点。
2. 递归排序：将链表从中间断开，对左右两半分别递归排序。
3. 合并：像拉链一样将两个有序链表交错合并。

自底向上优化

递归版本的空间复杂度为 O(log n)（调用栈）。自底向上版本从长度为1的子链表开始，逐轮倍增合并长度，完全消除递归栈，实现 O(1) 额外空间。

Java完整实现

/**
 * 链表排序：归并排序的递归与迭代实现
 */
public class LinkedListSort {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            ListNode cur = this;
            while (cur != null) {
                sb.append(cur.val);
                if (cur.next != null) sb.append(" -> ");
                cur = cur.next;
            }
            return sb.toString();
        }
    }

    /**
     * 方法一：递归归并排序（Top-Down）
     * 时间复杂度 O(n log n)，空间复杂度 O(log n)（递归栈）
     */
    public ListNode sortListRecursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 快慢指针找中点
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 断开链表
        ListNode mid = slow.next;
        slow.next = null;

        // 递归排序左右两半
        ListNode left = sortListRecursive(head);
        ListNode right = sortListRecursive(mid);

        // 合并两个有序链表
        return merge(left, right);
    }

    /**
     * 方法二：自底向上归并排序（Bottom-Up）
     * 时间复杂度 O(n log n)，空间复杂度 O(1)
     * 从长度为1开始，逐轮倍增合并
     */
    public ListNode sortListIterative(ListNode head) {
        if (head == null || head.next == null) return head;

        // 计算链表长度
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 步长从1开始，每次翻倍
        for (int step = 1; step < length; step <<= 1) {
            ListNode prev = dummy;
            ListNode curr = dummy.next;

            while (curr != null) {
                // 切出第一段长度为 step 的链表
                ListNode left = curr;
                ListNode right = split(left, step);
                // 切出第二段长度为 step 的链表
                curr = split(right, step);

                // 合并两段有序链表
                prev.next = merge(left, right);

                // prev 移动到合并后链表的末尾
                while (prev.next != null) {
                    prev = prev.next;
                }
            }
        }

        return dummy.next;
    }

    /**
     * 合并两个有序链表
     */
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }

        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    /**
     * 将链表从头部切出 n 个节点，返回剩余部分的头节点
     */
    private ListNode split(ListNode head, int n) {
        if (head == null) return null;
        ListNode cur = head;
        // 走 n-1 步到达第n个节点
        for (int i = 1; i < n && cur.next != null; i++) {
            cur = cur.next;
        }
        ListNode rest = cur.next;
        cur.next = null; // 断开
        return rest;
    }

    /**
     * 辅助方法：创建测试链表
     */
    public static ListNode createList(int[] arr) {
        if (arr.length == 0) return null;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int val : arr) {
            cur.next = new ListNode(val);
            cur = cur.next;
        }
        return dummy.next;
    }

    /**
     * 链表反转（额外练习）
     * 时间复杂度 O(n)，空间复杂度 O(1)
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    /**
     * 链表去重（保留一个重复元素）
     * 时间复杂度 O(n)，空间复杂度 O(1)
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    public static void main(String[] args) {
        LinkedListSort solution = new LinkedListSort();

        System.out.println("=== 链表归并排序演示 ===\n");

        int[] arr = {4, 2, 1, 3, 5, 8, 6, 7};
        ListNode head1 = createList(arr);
        System.out.println("原始链表: " + head1);
        ListNode sorted1 = solution.sortListRecursive(head1);
        System.out.println("递归排序: " + sorted1);

        ListNode head2 = createList(arr);
        ListNode sorted2 = solution.sortListIterative(head2);
        System.out.println("迭代排序: " + sorted2);

        // 测试链表反转
        System.out.println("\n链表反转: " + solution.reverseList(createList(new int[]{1, 2, 3, 4, 5})));

        // 测试去重
        System.out.println("去重 [1,1,2,3,3]: " 
            + solution.deleteDuplicates(createList(new int[]{1, 1, 2, 3, 3})));
    }
}

复杂度分析

扩展思考

1. 快速排序变体：链表虽不支持随机访问，但可用”三向切分”思路实现链表快速排序——以头节点为枢轴，将链表划分为 < pivot、== pivot、> pivot 三段，再递归排序首尾两段。
2. 多路归并：若有 k 个有序链表需合并为一个，可用优先队列（小顶堆）维护 k 个当前节点，时间复杂度 O(n log k)。
3. 链表判环与找入口：快慢指针的另一个经典应用——fast 走两步、slow 走一步，相遇后 slow 回到头节点，两者同步前进再次相遇点即为环入口。

链表排序是面试高频考点，而自底向上的归并排序更是考察候选人对指针操作细致程度的试金石。掌握这套”找中点-分治-合并”的范式，将为你解决绝大多数链表问题提供坚实的方法论基础。