148. 排序链表

题目：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例1：

解题思路：
这道题是一道综合题，考察了链表中间节点+合并有序链表。首先我们链表中间节点，然后从中间结点的前一个节点处断开，分为两段链表。
然后对这两段更短的链表分别调用sortList，得到两段有序的链表。
最后合并这两段有序链表并返回结果。
详细题解可参见https://leetcode.cn/problems/sort-list/solutions/2993518/liang-chong-fang-fa-fen-zhi-die-dai-mo-k-caei

/*** 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;}ListNode head2 = middleNode(head);head = sortList(head);head2 = sortList(head2);return mergeTwoList(head, head2);}private ListNode middleNode(ListNode head){ListNode pre = head, slow = head, fast = head;while(fast != null && fast.next != null){pre = slow;slow = slow.next;fast = fast.next.next;}pre.next = null;return slow;}private ListNode mergeTwoList(ListNode head, ListNode head2){ListNode dummy = new ListNode();ListNode cur = dummy;while(head != null && head2 != null){if(head.val <= head2.val){cur.next = head;head = head.next;}else{cur.next = head2;head2 = head2.next;}cur = cur.next;}cur.next = head != null ? head : head2;return dummy.next;}
}