归并排序链式存储代码

归并排序算法通常用于数组或列表的排序，但当处理链表时，我们可以使用类似的方法。由于链表的特殊性质（节点间的链接而非连续存储），我们需要修改归并过程来适应链表。以下是一个简单的归并排序链表的伪代码和概念：

// 假设链表节点定义为：
class ListNode {
    val: number
    next: ListNode | null
}

function mergeSortList(head: ListNode | null): ListNode | null {
    // 如果链表为空或者只有一个元素，直接返回
    if (!head || !head.next) return head;

    // 将链表拆分成两个子链表
    let slow = head, fast = head.next;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    const mid = slow.next;
    slow.next = null; // 断开两个子链表

    // 对两个子链表递归排序
    let left = mergeSortList(head);
    let right = mergeSortList(mid);

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

function merge(left: ListNode | null, right: ListNode | null): ListNode | null {
    let result = null, curr = null;
    while (left && right) {
        if (left.val <= right.val) {
            if (!result) result = left;
            left = left.next;
        } else {
            if (!result) result = right;
            right = right.next;
        }
    }
    // 如果其中一个链表已经遍历完，将另一个剩余部分添加到结果
    curr = result ? result : (left || right);
    while (curr) {
        curr = curr.next;
        result = result ? result.next : curr;
    }
    return result;
}