21.合并两个有序链表

题目说明

难度简单 示例 1：

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

示例 2:

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

示例 3：

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

解题思路

在解决合并两个有序链表的问题时，无论是递归还是非递归方法，解题思路的核心是保持链表的有序性。以下是两种方法的详细解题思路：

递归方法解题思路

1. 定义基本情况：递归算法需要一个或多个基本情况来终止递归调用。在这个场景中，如果l1或l2中的任一链表为空，递归就应该停止，因为空链表不需要合并。

2. 比较节点值：比较两个链表当前节点的值。

3. 递归合并较小节点：将较小节点的下一个节点与另一链表的当前节点进行递归合并。

4. 连接节点：将递归合并得到的链表连接到较小节点的后面。

5. 返回合并后的头节点：递归结束时返回合并后的链表的头节点。

递归方法的关键在于理解递归的终止条件和递归调用如何逐步构建出最终的有序链表。

非递归方法解题思路

1. 初始化虚拟头节点：创建一个虚拟头节点res，这样可以简化对空链表的处理，并使用一个指针tmp来追踪当前链表的末尾。

2. 使用循环遍历：使用while循环，当两个链表都非空时，进行节点的比较和合并。

3. 比较并连接节点：比较两个链表当前节点的值，将较小节点连接到tmp后面，并移动tmp和较小节点的指针。

4. 处理剩余链表：当其中一个链表遍历完时，将另一个链表的剩余部分直接连接到tmp后面。

5. 返回合并后的链表：最后返回虚拟头节点res的下一个节点，即合并后的有序链表的头节点。

非递归方法的关键在于使用循环来逐步构建合并后的链表，同时保持两个输入链表的有序性。

总结

• 递归方法：利用了递归的简洁性，通过递归调用解决了子问题，直到基本情况，然后逐步构建出最终的解决方案。这种方法在教学和理解上很有帮助，但在实际应用中可能需要考虑栈空间的限制。

• 非递归方法：通过迭代的方式逐步解决，避免了递归可能导致的栈溢出问题，通常在处理较长链表时更为高效。这种方法在实际编程中更为常见，尤其是在对性能有要求的应用中。

两种方法各有优势，选择哪一种取决于具体问题的需求、链表的长度以及个人对算法的偏好。

代码示例

递归代码如下：

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    // 基本情况：如果l1为空，直接返回l2
    guard let left = l1 else {
        return l2
    }
    // 基本情况：如果l2为空，直接返回l1
    guard let right = l2 else {
        return l1
    }
    
    // 如果left的当前节点值小于right的当前节点值
    if left.val < right.val {
        // 将left的下一个节点设置为递归调用的返回结果
        left.next = mergeTwoLists(left.next, right)
        // 返回left作为当前合并链表的头节点
        return left
    } else {
        // 否则，将right的下一个节点设置为递归调用的返回结果
        right.next = mergeTwoLists(left, right.next)
        // 返回right作为当前合并链表的头节点
        return right
    }
}

非递归代码如下：

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    // 创建一个虚拟头节点，避免处理空链表的特殊情况
    let res = ListNode(0)
    // 使用tmp指针来追踪合并链表的末尾
    var tmp = res
    // 初始化指向两个链表头节点的指针
    var left = l1
    var right = l2
    
    // 当两个链表都非空时，循环进行合并操作
    while left != nil && right != nil {
        // 如果left的当前节点值小于right的当前节点值
        if left!.val < right!.val {
            // 将left的当前节点连接到tmp后面
            tmp.next = left
            // 移动left指针到下一个节点
            left = left?.next
        } else {
            // 否则，将right的当前节点连接到tmp后面
            tmp.next = right
            // 移动right指针到下一个节点
            right = right?.next
        }
        // 移动tmp指针到下一个节点，准备连接下一个较小节点
        tmp = tmp.next!
    }
    
    // 如果left不为空，说明left还有剩余节点，直接连接到tmp后面
    if left == nil {
        tmp.next = right
    }
    // 如果right不为空，说明right还有剩余节点，直接连接到tmp后面
    if right == nil {
        tmp.next = left
    }
    
    // 返回虚拟头节点的下一个节点，即为合并后的有序链表的头节点
    return res.next
}