题解 | #牛群的身高排序# 快速排序（java）

import java.util.*;

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode pivot = head; // 选取头节点作为基准元素

        ListNode smallerHead = new ListNode(0); // 小于基准元素的链表
        ListNode smallerTail = smallerHead;

        ListNode equalHead = new ListNode(0); // 等于基准元素的链表
        ListNode equalTail = equalHead;

        ListNode greaterHead = new ListNode(0); // 大于基准元素的链表
        ListNode greaterTail = greaterHead;

        ListNode current = head;

        while (current != null) {
            if (current.val < pivot.val) { // 当前节点的值小于基准元素的值
                smallerTail.next = current;
                smallerTail = smallerTail.next;
            } else if (current.val >
                       pivot.val) { // 当前节点的值大于基准元素的值
                greaterTail.next = current;
                greaterTail = greaterTail.next;
            } else { // 当前节点的值等于基准元素的值
                equalTail.next = current;
                equalTail = equalTail.next;
            }
            current = current.next;
        }

        smallerTail.next = null; // 小于基准元素的链表末尾置空
        greaterTail.next = null; // 大于基准元素的链表末尾置空
        equalTail.next = null; // 等于基准元素的链表末尾置空

        ListNode sortedSmaller = sortList(
                                     smallerHead.next); // 对小于基准元素的链表排序
        ListNode sortedGreater = sortList(
                                     greaterHead.next); // 对大于基准元素的链表排序

        ListNode result = concat(sortedSmaller,
                                 equalHead.next); // 连接排好序的三部分链表
        result = concat(result, sortedGreater);

        return result;
    }

    private ListNode concat(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        ListNode current = head1;
        while (current.next != null) {
            current = current.next;
        }
        current.next = head2;
        return head1;
    }
}

该题主要考察的知识点就是链表和排序算法。

代码：

1. 判断链表是否为空或只有一个节点，如果是，则无需排序，直接返回链表。
2. 选取一个基准元素，可以选择链表的头节点作为基准元素。
3. 创建三个指针smallerHead、greaterHead和equalHead，分别用于指向小于基准元素的链表、大于基准元素的链表和等于基准元素的链表的头节点。
4. 遍历链表，根据节点的值与基准元素的比较结果，将节点插入到对应的链表中。遍历完成后，原链表被拆分成三个部分。
5. 分别对小于基准元素的链表、大于基准元素的链表和等于基准元素的链表进行递归排序。得到排好序的三个链表。
6. 将三个排好序的链表连接起来，返回排好序的链表。
7. 在递归排序的过程中，使用concat函数将排好序的链表连接起来。
8. 最终返回排好序的链表。