单链表排序（归并排序）

图解：

链接

思路：

1.用归并排序（分治和合并）

2.先用三个指针：pre和快指针（fast）和慢指针（mid）找到链表的中间的节点，将链表分为两个小的子链表

3.再进行向下递归（划分区间）和向上递归（合并）

4.合并的时候就进行大小比较，利用归并排序的思想进行合并

代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode Merge(ListNode head1,ListNode head2){
        //合并函数
        //如果发现其中的一个链表是空的，则就不需要进行合并了，只需要返回另一个非空的链表即可
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        //创建一个新的链表的虚的头结点和一个cur指针
        ListNode dummynode=new ListNode(-1);
        ListNode cur=dummynode;
        //利用归并的思想进行判断，只要两个指针还没有到达null,就一直进行，直到有一个表遍历完了
        //进行比较值的大小，分情况讨论，将值较小的节点连接到新的链表中
        //最后将没有判断过大小的部分连接到新形成的表中
        while(head1!=null&&head2!=null){
           if(head1.val<=head2.val){
                    cur.next=head1;
                    head1=head1.next;
            }else{
                    cur.next=head2;
                    head2=head2.next;
             }
                cur=cur.next;
        }
        if(head1==null){
            cur.next=head2;
        }
        if(head2==null){
            cur.next=head1;
        }
       return dummynode.next;


    }
    public ListNode sortInList (ListNode head) {
        //判断一下如果当前的表为空或者是只有一个节点，那么就表示向下递归到达
        //了终点条件，因为当没有节点和只有一个节点的时候本身就是有序的，就可以直接返回
       if(head==null||head.next==null){
            return head;
       }
       //为了找到区间的中点进行分治，可以用三个指针：pre（即mid的前一个指针）、mid（慢指针，指向对半的位置）、fast（快指针）
       //由于让快指针的速度是慢指针的两倍，所以当快指针到达链表的结尾的时候,慢指针刚好到达中间点的后一个位置，让pre指向null,就是断开形成两个子链表
       ListNode pre=head;
       ListNode mid=head.next;
       ListNode fast=head.next.next;
       while(fast!=null&&fast.next!=null){
            pre=pre.next;
            mid=mid.next;
            fast=fast.next.next;
       }
       pre.next=null;
       //用递归的思想向下分治，向上合并，两个子区间的头结点分别是head和mid
       return Merge(sortInList(head),sortInList(mid));
    }
}