本文主要是介绍【注释详细，思路清晰】【打卡第13天】leetcode热题HOT100之Java实现：148. 排序链表，链表的归并排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
之前做过的是数组的归并排序，链表其实是一样的。
1、题目描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
2、算法分析
① sortList（list）对链表进行排序:
Input: 4->2->1->3 Output: 1->2->3->4
Input: -1->5->3->4->0 Output: -1->0->3->4->5
② 找到归并拆分的结点，注意 fast.next != null && fast.next.next != null
下面是分割，分成两个链表，一个是以head为头结点，另一个是以right为头结点的链表
图解：
合并的话，抽出来一个方法合并就可以。
3、代码实现
/*** 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 {public ListNode sortList(ListNode head) {if(head == null || head.next == null){return head;}// 定义两个指针slow，fast，目的是确定两个分链表,均指向head结点ListNode slow = head;ListNode fast = head;// 链表都往右走，找到分界点while(fast.next != null && fast.next.next != null){slow = slow.next;fast = fast.next.next;}// 定义右半链表的开始节点ListNode right = slow.next;// 左右结点断开slow.next = null;return merge(sortList(head),sortList(right));}// 只需要比较左右结点的值即可，比较结果合并public ListNode merge(ListNode head,ListNode right){if(head == null){return right;}if(right == null){return head;}// 创建一个新的链表存储结果ListNode result = new ListNode(0);if(head.val < right.val){result = head;result.next = merge(head.next,right);}else {result = right;result.next = merge(head,right.next);}return result;}
}
现在在听消愁，一杯敬明天，一杯敬过往；
这篇关于【注释详细，思路清晰】【打卡第13天】leetcode热题HOT100之Java实现：148. 排序链表，链表的归并排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
