Day73 排序链表

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

https://leetcode-cn.com/problems/sort-list/

你可以在 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

Java解法

思路：

• 将链表切割为已排序与未排序两个链表然后按顺序插入，
• 参考官方解：使用归并分割链表，再使用合并有序链表完成后续操作

package sj.shimmer.algorithm.m4_2021;

import sj.shimmer.algorithm.ListNode;

/**
 * Created by SJ on 2021/4/10.
 */

class D73 {
    public static void main(String[] args) {
        ListNode node = ListNode.createNode(new int[]{4, 2, 1, 3});
        System.out.println(sortList(node));
    }

    public static ListNode sortList(ListNode head) {
        return spiltByMidSort(head,null);
    }

    public static ListNode spiltByMidSort(ListNode head,ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        if (fast!=tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast!=tail) {
                fast = fast.next;
            }
        }
        ListNode midH = slow;
        ListNode n1 = spiltByMidSort(head,midH);
        ListNode n2 = spiltByMidSort(midH,tail);
        return mergeTwoLists(n1,n2);
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null&&l2 == null) {
            return null;
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = null;
        if (l1.val>l2.val) {
            head = l2;
            head.next = mergeTwoLists(l1,l2.next);
        }else {
            head = l1;
            head.next = mergeTwoLists(l1.next,l2);
        }
        return head;
    }
}

image

官方解

https://leetcode-cn.com/problems/sort-list/solution/

1. 自顶向下归并排序

   参考解，如上

   • 时间复杂度：O(nlogn)
   • 空间复杂度：O(logn)

2. 自底向上归并排序

   直接分解节点，再两两合并

   • 时间复杂度：O(nlogn)
   • 空间复杂度：O(1)