题目比较简单，使用链表的归并排序

解法都在代码里，不懂就留言或者私信

合并链表部分没怎么加注释，时间实在是不充裕，看不懂的看一下这篇专门讲解合并链表的

Leetcode面试经典150题-21.合并两个有序链表-CSDN博客

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {/**本题采用归并排序的思路：把链表分为左右两个部分，分别进行归并排序然后进行两个部分的merge过程，这个过程就是说合并两个有序链表的过程 */public ListNode sortList(ListNode head) {ListNode cur = head;/**找一下tail，这是最容易想到的，反正也就是O(n)的时间复杂度 */while(cur != null && cur.next != null) {cur = cur.next;}/**cur是最后一个节点，也就是tail */return mergeSortList(head, cur);}/**归并排序head~tail这个区间*/public ListNode mergeSortList(ListNode head, ListNode tail) {/**如果区间就一个节点，直接返回 */if(head == tail) {return head;}/**如果区间有两个节点，直接mergeList*/if(head.next == tail) {/**merge之前断开链接，不然就跑不完了 */head.next = null;return mergeList(head, tail);}/**开始使用快慢指针找中点 */ListNode slow = head, fast = head;/**确保fast在head~tail范围内，如果它是tail或者它的next是tail就终止循环 */while(fast != tail && fast.next != tail) {/**fast和slow先各走一步 */slow = slow.next;/**快指针每次走两步 */fast = fast.next.next;}/**出循环的时候fast是tail或者tail的前一个，然后slow是上班段最后一个节点,断开slow和后面链表的连接断开之前先拿到后半段的最后一个节点*/ListNode rightFirst = slow.next;slow.next = null;/**归并排序前半段 */ListNode list1 = mergeSortList(head, slow);/**不要管fast，终点是tail*/ListNode list2 = mergeSortList(rightFirst, tail);/**合并前后两个有序链表*/ListNode merged = mergeList(list1, list2);return merged;}/**合并两个有序链表的解法：除了这种方式也可以前面加个dummyNode，这样最后返回dummyNode下一个就行了 */public ListNode mergeList(ListNode list1, ListNode list2) {if(list1 == null) return list2;if(list2 == null) return list1;ListNode head = list1.val <= list2.val? list1 : list2;list1 = list1 == head? list1.next : list1;list2 = list2 == head? list2.next : list2;ListNode last = head;while(list1 != null && list2 != null) {if(list1.val <= list2.val) {last.next = list1;last = list1;list1 = list1.next;} else {last.next = list2;last = list2;list2 = list2.next;}}/**退出上面的while循环要么是list1用完了，要么是list2用完了，如果某个链表没有用完，就直接串到最后*/if(list1 != null) {last.next = list1;}if(list2 != null) {last.next = list2;}return head;}
}

没有特别好的解法，能过就行吧，时间复杂度都一样