Frontend Interview

Appearance

21. 合并两个有序链表 ​

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/

代码 ​

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 mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    let list = new ListNode(0, null);
    let head = list;
    while(list1 && list2){
        if(list1.val <= list2.val){
            list.next = list1;
            list1 = list1.next;
        }
        else{
            list.next = list2;
            list2 = list2.next;
        }
        list = list.next;
    }
    list.next = list1 ? list1 : list2;
    return head.next;
};

思路 ​

使用迭代法合并两个有序链表：

  1. 创建哑节点 head 作为结果链表的起始点
  2. 使用指针 list 指向当前构建位置
  3. 比较两个链表的当前节点：
    • 选择值较小的节点连接到结果链表
    • 移动被选中链表的指针
    • 移动结果链表的指针
  4. 当其中一个链表遍历完后，将另一个链表的剩余部分直接连接到结果链表
  5. 返回 head.next（跳过哑节点）

关键点 ​

  • 使用哑节点简化边界处理

  • 每次选择两个链表中较小的节点

  • 最后直接连接剩余部分，无需逐个遍历

  • 时间复杂度 O(m+n)，其中 m 和 n 分别是两个链表的长度

  • 空间复杂度 O(1)，只使用常数额外空间