Java 题解 | #牛群的身高排序#

该题考察链表的数据结构，以及排序算法。要对链表进行升序排序，可以使用归并排序的思想。

首先，我们需要实现一个合并两个有序链表的函数。然后，我们将链表逐步拆分为更小的子链表，直到每个子链表只有一个节点。接下来，我们将这些子链表两两合并，直到最终合并为一个完整的有序链表。

使用归并排序对链表进行排序的时间复杂度为 O(NlogN)，其中 N 是链表中的节点数。这是因为在每一层递归中，我们对链表进行了一次完整的遍历，并且每个节点都被比较和移动了一次。

• 首先，定义了一个 ListNode 类来表示链表的节点。每个节点包含一个整数值 val 和一个指向下一个节点的指针 next。
• 创建了一个名为 Solution 的类，其中包含了用于排序链表的方法 sortList。
• 在 sortList 方法中，首先检查边界条件，即链表为空或只有一个节点时，无需排序，直接返回链表头节点 head。
• 调用 findMiddle 方法找到链表的中点，将链表分成两部分。这里使用了快慢指针的技巧，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针正好指向中点位置。
• 将链表分成两部分后，将中点节点的 next 指针置空，将左半部分链表从头节点到中点节点进行排序，递归调用 sortList 方法。
• 将右半部分链表从中点节点的下一个节点到链表末尾进行排序，同样递归调用 sortList 方法。
• 调用 merge 方法，将排序后的左右两个子链表进行合并。首先创建一个哑节点 dummy 作为合并后链表的头节点，同时创建一个指针 curr 指向当前节点。
• 在 merge 方法中，使用循环比较两个链表的节点值大小，将较小的节点连接到合并后链表中，并将对应链表的指针向后移动。直到其中一个链表为空。
• 循环结束后，将剩余非空链表的部分直接连接到合并后链表的末尾。
• 返回哑节点 dummy 的下一个节点，即为排序后的链表的头节点。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode sortList (ListNode head) {
        // write code here
          // 边界条件：当链表为空或只有一个节点时，无需排序，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 找到链表的中点，将链表分成两部分
        ListNode mid = findMiddle(head);
        ListNode rightHead = mid.next;
        mid.next = null;

        // 递归地对两个子链表进行排序
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

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

    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;

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

        return slow;
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

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

        // 将剩余节点连接到合并后的链表的末尾
        curr.next = (l1 != null) ? l1 : l2;

        return dummy.next;
    }
}