007-合并两个有序链表 (Merge Two Sorted Lists)

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

解题思路

使用迭代法，比较两个链表的当前节点值，将较小的节点添加到结果链表中，然后移动对应的指针。使用一个虚拟头节点来简化操作。

JavaScript 解决方案

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoLists = (l1, l2) => {
    // 创建虚拟头节点
    const dummy = new ListNode(0);
    let current = dummy;
    
    // 比较两个链表的节点
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    // 处理剩余的节点
    current.next = l1 || l2;
    
    return dummy.next;
};

复杂度分析

时间复杂度：O(n + m)，其中 n 和 m 分别是两个链表的长度
空间复杂度：O(1)，只使用了常数额外空间

测试用例

// 创建链表的辅助函数
const createLinkedList = (arr) => {
    if (arr.length === 0) return null;
    const head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
};

// 将链表转换为数组的辅助函数
const linkedListToArray = (head) => {
    const result = [];
    let current = head;
    while (current) {
        result.push(current.val);
        current = current.next;
    }
    return result;
};

// 测试函数
const testMergeTwoLists = () => {
    const testCases = [
        {
            l1: [1, 2, 4],
            l2: [1, 3, 4],
            expected: [1, 1, 2, 3, 4, 4]
        },
        {
            l1: [],
            l2: [],
            expected: []
        },
        {
            l1: [],
            l2: [0],
            expected: [0]
        },
        {
            l1: [1, 3, 5],
            l2: [2, 4, 6],
            expected: [1, 2, 3, 4, 5, 6]
        },
        {
            l1: [1, 2, 3],
            l2: [4, 5, 6],
            expected: [1, 2, 3, 4, 5, 6]
        },
        {
            l1: [4, 5, 6],
            l2: [1, 2, 3],
            expected: [1, 2, 3, 4, 5, 6]
        }
    ];

    testCases.forEach((testCase, index) => {
        const l1 = createLinkedList(testCase.l1);
        const l2 = createLinkedList(testCase.l2);
        const result = mergeTwoLists(l1, l2);
        const resultArray = linkedListToArray(result);
        const passed = JSON.stringify(resultArray) === JSON.stringify(testCase.expected);
        
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: l1 = [${testCase.l1}], l2 = [${testCase.l2}]`);
        console.log(`期望: [${testCase.expected}], 实际: [${resultArray}]\n`);
    });
};

// 运行测试
testMergeTwoLists();

关键点总结

虚拟头节点：使用虚拟头节点简化操作，避免处理头节点的特殊情况
指针移动：比较节点值后移动对应的指针
剩余节点：处理一个链表遍历完后的剩余节点
边界处理：空链表的处理
内存管理：注意不要修改原始链表的结构

总结

这道题考察了以下重点：

链表操作：理解链表的基本操作和指针移动
合并算法：掌握两个有序序列的合并技巧
虚拟头节点：使用虚拟头节点简化代码
边界处理：对各种边界情况的考虑

迭代法是最优解，时间复杂度为 O(n + m)，空间复杂度为 O(1)。在实际面试中，建议先解释算法思路，然后实现代码。

007-合并两个有序链表 (Merge Two Sorted Lists)

On this page