[148] 排序链表

1. 归并排序（Merge Sort）：归并排序是一种有效的排序算法，适用于链表。它的时间复杂度为 $O(n log n)$，空间复杂度为 $O(log n)$（递归调用栈的空间复杂度）。

2. 插入排序（Insertion Sort）：插入排序也可以用来对链表排序，时间复杂度为 $O(n^2)$，但实现起来相对简单。

归并排序

归并排序是一种分治算法，先将链表分成两半，对每半链表递归排序，然后合并两个已排序的链表。归并排序特别适合链表，因为链表可以在 O(1) 时间内进行合并操作。

details

// 定义链表节点类
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function sortList(head) {
    if (!head || !head.next) {
        return head;
    }

    // 分割链表
    let mid = getMiddle(head);
    let left = head;
    let right = mid.next;
    mid.next = null;

    // 递归排序两半链表
    left = sortList(left);
    right = sortList(right);

    // 合并两个已排序链表
    return merge(left, right);
}

function getMiddle(head) {
    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

function merge(left, right) {
    let dummy = new ListNode(0);
    let current = dummy;

    while (left && right) {
        if (left.val < right.val) {
            current.next = left;
            left = left.next;
        } else {
            current.next = right;
            right = right.next;
        }
        current = current.next;
    }

    if (left) {
        current.next = left;
    } else {
        current.next = right;
    }

    return dummy.next;
}

1. 分割链表:

   • 使用快慢指针找出链表的中间节点，将链表分成两半。

2. 递归排序:

   • 递归地对链表的左半部分和右半部分进行排序。

3. 合并链表:

   • 使用归并操作将两个已排序的链表合并成一个已排序的链表。

插入排序

插入排序相对简单，但在链表上的时间复杂度较高。实现步骤包括创建一个新的链表，将节点逐一插入到合适的位置。

details

var sortList = function (head) {
    if (!head || !head.next) return head;

    let dummy = new ListNode(-Infinity);

    let cur = head;
    while (cur !== null) {
        let prev = dummy;
        let next = dummy.next;
        while (next !== null && next.val < cur.val) {
            prev = next;
            next = next.next;
        }

        let temp = cur.next;

        // next 链接到 dummy 上
        prev.next = cur;
        cur.next = next;

        cur = temp;
    }
    return dummy.next;
};