链表归并排序算法详解

归并排序是一种高效的排序算法，其基本思想是将数据分为若干小部分，分别排序后再合并。对于链表而言，这一过程涉及到链表的分割、排序和合并三个主要步骤。

首先，我们需要定义一个链表节点类：

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

接下来，我们实现链表的归并排序：

class Solution {    // 获取链表的中间节点    private ListNode getMid(ListNode head) {        if (head == null || head.next == null) {            return 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 sortList(ListNode head) {        if (head == null || head.next == null) {            return head;        }        // 分割链表为两部分        ListNode midNode = getMid(head);        ListNode right = midNode.next;        midNode.next = null;        // 递归排序左右两部分        ListNode leftNode = sortList(head);        ListNode rightNode = sortList(right);        // 合并已排序的部分        return merge(leftNode, rightNode);    }    // 合并两个有序链表    private ListNode merge(ListNode left, ListNode right) {        ListNode dummy = new ListNode(0);        ListNode current = dummy;        while (left != null && right != null) {            if (left.val 

以上代码展示了如何通过归并排序对链表进行排序。首先，我们定义了一个链表节点类，并实现了获取中间节点的方法。然后，通过递归的方式将链表分割成两部分，分别排序后，再将它们合并成一个有序的链表。