leetcode——排序链表（java）

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

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

解题方法：（归并排序（分治））

1. sortList(ListNode head): 归并排序。（函数中的两次递归分别时对当前的链表进行前后两部分进行拆分，最后才能进行排序重组）

2.middleNode(ListNode head): 找到链表中点并拆分。（将head拆成了两部分，前半部分与后半部分，返回的时候后半部分。）

3.mergeTwoLists(ListNode list1, ListNode list2): 合并两个有序链表。（将两个链表进行比较排序然后重组）

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