Frontend Interview

Appearance

148. 排序链表 ​

题目链接：https://leetcode.cn/problems/sort-list/

代码 ​

ts
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function sortList(head: ListNode | null): ListNode | null {
    // 归并排序
    if(head === null || head.next === null){
        return head;
    }
    let mid = midNode(head);
    return mergeSort(sortList(head), sortList(mid));
};

function midNode(head){
    let pre = head, slow = head, fast = head;
    while(fast && fast.next){
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    pre.next = null;
    return slow;
}

function mergeSort(left, right) {
    let dummy = new ListNode();
    let now = dummy;
    while (left && right) {
        if (left.val < right.val) {
            now.next = left;
            left = left.next;
        }
        else {
            now.next = right;
            right = right.next;
        }
        now = now.next;
    }
    now.next = left ?? right;
    return dummy.next;
}

思路 ​

使用归并排序对链表进行排序：

主要步骤 ​

  1. 递归终止条件：
    • 如果链表为空或只有一个节点，直接返回
  2. 找到链表的中间节点，将链表分为两部分
  3. 递归排序左右两部分
  4. 合并两个有序链表

辅助函数 ​

midNode：找到链表的中间节点并断开

  • 使用快慢指针找到中间节点
  • 使用 pre 指针记录慢指针的前一个节点
  • 断开链表：pre.next = null
  • 返回中间节点（右半部分的起始节点）

mergeSort：合并两个有序链表

  • 创建哑节点 dummy
  • 比较两个链表的节点值，选择较小的连接到结果链表
  • 处理剩余部分：now.next = left ?? right

关键点 ​

  • 归并排序是链表排序的最佳选择，时间复杂度稳定

  • 通过断开链表避免无限递归

  • 递归分治思想：分解 → 递归 → 合并

  • 时间复杂度 O(nlog⁡n)，其中 n 是链表的长度

  • 空间复杂度 O(log⁡n)，递归调用栈的深度