题解 | #单链表的排序#

问题描述

假设你有一串珠子，每颗珠子上都有一个数字。这串珠子现在是乱序的，我们要按照数字从小到大的顺序重新排列它们。

解决方法

我们可以想象一下，如果你有一堆卡片，每张卡片上有一个数字，你想把这些卡片按数字大小顺序排列好，你会怎么做呢？

1. 找到中间点

首先，我们需要找到这串珠子的中间位置。就像玩绳子游戏一样，我们可以用两只手来找到中间的位置：

• 一只手指一颗一颗地移动（慢指针）。
• 另一只手指两颗两颗地移动（快指针）。
• 当快速移动的手指无法再移动时，慢速移动的手指就在中间位置了。

2. 分成两半

找到中间位置后，我们可以把这串珠子分成两半。就像你把一串项链分成两个部分一样。

3. 分别排序

接下来，我们对这两半珠子分别进行同样的操作：

• 找到中间点
• 分成两半
• 分别排序

一直重复这个过程，直到每半只有很少的珠子，甚至是只有一个珠子。

4. 合并

最后，我们要把所有的小部分珠子合并成一大串，但这次要确保数字是从小到大排列的。就像你在整理书本时，一本一本按照编号放好。

具体步骤

假设你有这样一串珠子：1, 3, 2, 4, 5。

1. 找到中间点：
1. 我们发现中间点是 3。
2. 分成两半：
1. 珠子变成两串：1, 3 和 2, 4, 5。
3. 对每一半排序：
1. 对 1, 3 排序：
1. 已经是有序的了。
2. 对 2, 4, 5 排序：
1. 先找到中间点 4，分成 2 和 4, 5，再分别排序。
4. 合并：
1. 把 1 和 3 合并成 1, 3。
2. 把 2 和 4, 5 合并成 2, 4, 5。
3. 最后把 1, 3 和 2, 4, 5 合并成 1, 2, 3, 4, 5。

代码实现

下面是一个简单的 Java 实现：

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    /**
     * 对链表进行排序。
     * @param head 链表的头节点
     * @return 排序后的链表的头节点
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head; // 如果链表为空或只有一个元素，直接返回
        }

        // 找到中间点
        ListNode middle = getMiddle(head);
        ListNode right = middle.next;
        middle.next = null; // 分成两半

        // 递归排序两半
        ListNode leftSorted = sortList(head);
        ListNode rightSorted = sortList(right);

        // 合并两半
        return merge(leftSorted, rightSorted);
    }

    private ListNode getMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next; // 慢指针
            fast = fast.next.next; // 快指针
        }

        return slow;
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

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

        // 连接剩余的部分
        if (left != null) {
            tail.next = left;
        } else {
            tail.next = right;
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        // 创建链表
        ListNode head = new ListNode(1);
        head.next = new ListNode(3);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5); // 代表数字 [1, 3, 2, 4, 5]

        // 创建Solution对象
        Solution solution = new Solution();

        // 调用sortList方法
        ListNode sortedHead = solution.sortList(head);

        // 输出结果
        while (sortedHead != null) {
            System.out.print(sortedHead.val + " ");
            sortedHead = sortedHead.next;
        }
    }
}