题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
输入：head = [4,2,1,3]
输出：[1,2,3,4]

题目分析

可以使用 ArrayList 或者 PriorityQueue 来存储结点，然后排序，时间复杂度 O(n * logn)，但都需要额外开辟空间 O(n)

如果不额外开辟空间，则可以归并排序：
1. 找出链表中点，将链表分为2个子链表
2. 递归调用，对子链表进行排序
3. 合并两个子链表
时间复杂度 O(n * logn)

Java

public ListNode sortList(ListNode head) {
    // 递归出口
    if (head == null || head.next == null) {
        return head;
    }

    // 找出中点
    ListNode p1 = head, p2 = head.next;
    ListNode mid = head;
    while (p2 != null && p2.next != null) {
        mid = p1;
        p1 = p1.next;
        p2 = p2.next;
        p2 = p2.next;
    }

    // 递归排序子链表
    ListNode left = head;
    ListNode right = mid.next;
    mid.next = null;
    left = sortList(left);
    right = sortList(right);

    // 合并左右子链表
    ListNode ans = new ListNode();
    ListNode cur = ans;
    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;
    }
    if (left != null) {
        cur.next = left;
    }
    if (right != null) {
        cur.next = right;
    }

    return ans.next;
}

Kotlin

fun sortList(head: ListNode?): ListNode? {
    // 递归出口
    if (head?.next == null) {
        return head
    }


    // 寻找中点
    var slow = head!!
    var fast = head.next
    while (fast?.next != null) {
        slow = slow.next!!
        fast = fast.next?.next
    }

    // 递归排序子链表
    var left = head
    val mid = slow
    var right = mid.next
    mid.next = null
    left = sortList(left)
    right = sortList(right)

    // 合并子链表
    val ans = ListNode(0)
    var cur = ans
    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!!
    }
    if (left != null) {
        cur.next = left;
    }
    if (right != null) {
        cur.next = right;
    }

    return ans.next
}