题目：

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

示例 1：

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

思路：

1.找链表中点【使用快慢指针  慢指针每次移动一步，快指针每次移动两步，当快指针移动到链表末尾时，慢指针则指向中点位置】

2.对两个链表分别进行递归排序

3.合并两个链表

代码：

/**
 * 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) {
        return sort(head, null);
    }
    // 使用归并排序 将链表一分为二 分别递归进行排序  对head-tail进行归并排序
    public ListNode sort(ListNode head, ListNode tail){
        // 链表判空 直接返回NULL
        if(head == null){
            return head;
        }
        if(head.next == tail){
            // 如果只有一个节点 就返回这一个节点
            head.next = null;
            return head;
        }

        // 使用快慢指针找到链表中点 慢指针移动一步，快指针移动两步
        ListNode slow = head;
        ListNode fast = head;
        while(fast != tail){
            slow = slow.next;
            fast = fast.next;
            if(fast != tail){
                fast = fast.next;
            }
        }
        // 经过快慢指针 slow指向中点节点
        ListNode mid = slow;
        // 递归调用归并排序
        ListNode list1 = sort(head,mid);
        ListNode list2 = sort(mid, tail);
        // 合并两个链表
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    // 合并两个已经排序的链表
    public ListNode merge(ListNode head1, ListNode head2){
        // 创建哑铃节点 作为合并链表的起始节点
        ListNode dummyHead = new ListNode(0);

        // temp用于遍历链表  temp1和temp2分别指向两个待合并链表的当前节点 
        ListNode temp = dummyHead;
        ListNode temp1 = head1;
        ListNode temp2 = head2;

        // 遍历两个链表 升序连接
        while(temp1 != null && temp2 != null){
            if(temp1.val <= temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;

            }else{
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        // 如果其中一个链表已经遍历完，则将剩余链表连接到temp中
        if(temp1 != null){
            temp.next = temp1;

        }else{
            temp.next = temp2;
        }
        return dummyHead.next;

    }
}