Leetcode top100之链表排序

148. 排序链表 - 力扣（LeetCode）

思路比较巧妙

1.使用快慢指针，找到链表的中间节点

2.断开中间连接，对两端递归排序

3.合并两个链表

有快慢指针的技巧和合并链表的技巧

注意点：

快慢指针起点，slow=head，fast=head.next

链表排序前，注意返回头，排完序后，链表头是变化的

    public ListNode sortList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode mid = getMidNode(head);ListNode temp = mid.next;mid.next = null;ListNode left = sortList(head);ListNode right = sortList(temp);return mergeList(left,right);}private ListNode mergeList(ListNode l1, ListNode l2) {ListNode pre = new ListNode(-1);ListNode now = pre;while (l1 != null && l2 != null) {if (l1.val > l2.val) {now.next = l2;l2 = l2.next;now = now.next;} else {now.next = l1;l1 = l1.next;now = now.next;}}if (l1 != null) {now.next = l1;}if (l2 != null) {now.next = l2;}return pre.next;}private ListNode getMidNode(ListNode head) {ListNode slow= head;ListNode fast = head.next;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}