题目链接：
链接
题目描述：
思路：
归并排序
递归实现
用双指针找到中间点，然后把链表分成两个部分，不断进行这个操作，直到next或当前节点为null
返回当前节点，回到“上一步”
在“上一步”里，把返回的节点接受为自己的左右两段部分的头结点
然后根据大小进行合并
相邻节点直接合并
省去拆分的操作，直接合并相邻的节点
实现代码：
class Solution {public ListNode sortList(ListNode head) {if(head == null || head.next == null){return head;}ListNode fast = head.next , slow = head;//分割while(fast != null && fast.next!= null){fast = fast.next.next;slow = slow.next;}ListNode tmp = slow.next;slow.next = null;//再分割ListNode left = sortList(head);ListNode right = sortList(tmp);//虚拟头ListNode dummy = new ListNode(0);ListNode cur = dummy;//合并while(left != null && right != null){if(left.val < right.val){cur.next = left;left = left.next;} else{cur.next = right;right = right.next; }cur = cur.next;}cur.next = left != null ? left : right;return dummy.next;}
}
class Solution {public ListNode sortList(ListNode head) {if(head == null){return head;}int length = 0;ListNode node = head;while(node != null){length++;node = node.next;}ListNode dummy = new ListNode(0,head);for(int sublength = 1; sublength < length; sublength = sublength *2){ListNode pre = dummy, cur = dummy.next;while(cur != null){//找到第1段ListNode head1 = cur;for(int i = 1; i < sublength && cur.next != null; i++){cur = cur.next;}ListNode head2 = cur.next;cur.next = null;//找到第2段cur = head2;for(int i = 1; i < sublength && cur != null && cur.next != null ; i++){cur = cur.next;}//找到剩下的,下一次while就是合并剩下的里面前两段ListNode next = null;if(cur != null){next = cur.next;cur.next = null;}//合并ListNode merged = merge(head1,head2);pre.next = merged;while(pre.next != null){pre = pre.next;}cur = next;}}return dummy.next;}public ListNode merge(ListNode head1, ListNode head2){ListNode dummy = new ListNode(0);ListNode tmp = dummy, tmp1 = head1, tmp2 = head2;while(tmp1 != null && tmp2 != null){if(tmp1.val <= tmp2.val){tmp.next = tmp1;tmp1 = tmp1.next;}else{tmp.next = tmp2;tmp2 = tmp2.next;}tmp = tmp.next;}tmp.next = tmp1 != null ? tmp1 : tmp2;return dummy.next;}
}
