算法练习(3) - 链表排序

package top.buukle.buukle.排序类;

public class 排序链表 {

    //给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
//
// 进阶：
//
//
// 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
//
//
//
//
// 示例 1：
//
//
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
//
//
// 示例 2：
//
//
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
//
//
// 示例 3：
//
//
//输入：head = []
//输出：[]
//
//
//
//
// 提示：
//
//
// 链表中节点的数目在范围 [0, 5 * 104] 内
// -105 <= Node.val <= 105
//
// Related Topics 排序 链表
// 👍 1179 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 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; }
     * }
     */

 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 slow = head;
            ListNode fast = head.next;

            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            // 初始化后半截儿
            ListNode after =  slow.next;
            // 切断链表
            slow.next = null ;
            // 递归调用并排序
            ListNode left = sortList(head);
            ListNode right = sortList(after);

            ListNode res = new ListNode();
            ListNode h = res;

            while(left != null && right != null){
                if(left.val < right.val){
                    h.next = left;
                    left = left.next;
                }else{
                    h.next = right;
                    right = right.next;
                }
                h = h.next;
            }
            h.next = left == null ? right : left;
            return res.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}