简述Java单链表归并排序 ？

归并排序是一种经典的排序算法，其基本思想是将两个或两个以上的有序表合并成一个新的有序表。在单链表的归并排序中，我们首先需要将链表分割成多个子链表，每个子链表都是有序的，然后再将这些子链表合并成一个有序的大链表。

以下是一个基本的Java实现，这个实现使用递归的方式来分解和合并链表：

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

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

        // 使用快慢指针找到链表的中点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 分割链表
        ListNode mid = slow.next;
        slow.next = null;

        // 递归排序左右两个子链表
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

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

    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;
        }

        // 将剩余的部分连接到结果链表的末尾
        if (l1 != null) {
            curr.next = l1;
        } else if (l2 != null) {
            curr.next = l2;
        }

        return dummy.next;
    }
}

这个实现首先通过快慢指针找到链表的中点，然后将链表分割成两个子链表。接着，递归地对这两个子链表进行排序。最后，使用merge函数将两个有序链表合并成一个有序链表。

需要注意的是，这个实现的时间复杂度是O(n log n)，其中n是链表的长度。这是因为每次递归都会将链表长度减半，而合并两个有序链表的时间复杂度是O(n)。因此，总的时间复杂度是O(n log n)。空间复杂度是O(log n)，这是因为递归栈的深度最多为log n。