LeetCode 21：合并两个有序链表，简单却不简单

大家好！我是王大神，今天我们来聊一下LeetCode上的一个题目——合并两个有序链表（LeetCode 21）。这个题目看似简单，实则包含了链表操作的多个基础知识点。既然这么有趣，我们就一起来探究一下吧！

题目概述

首先，让我们来看看这个题目到底在说什么。简单来说，这个题目要求你把两个有序的链表合并成一个新的有序链表，并返回新链表的头节点。说人话，就是把两个排好队的人群合并成一个更大的排好队的人群。

为什么要合并有序链表？

你可能会问，有序链表合并有什么用呢？其实，在真实的应用场景中，这个技术能帮助我们高效地整合信息和数据。想象一下，两个不同的数据库都有各自排序好的数据，如果我们想整合这两个数据库，合并有序链表就派上用场了。

如何合并？

递归解法

一个简单的方法是使用递归。具体思路是这样的：

1. 比较两个链表头节点的值。
2. 选择值较小的节点作为新链表的当前节点。
3. 递归地合并剩下的节点。

Python代码如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    if not l1:
        return l2
    if not l2:
        return l1

    if l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

迭代解法

除了递归，我们还可以使用迭代来解决这个问题。

1. 创建一个虚拟头节点。
2. 用一个指针跟踪新链表的最后一个节点。
3. 比较两个链表的当前节点，将较小的节点接在新链表后。
4. 重复以上步骤，直到某个链表为空。

Python代码如下：

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    current = dummy

    while l1 and 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 or l2

    return dummy.next

一句话总结

合并两个有序链表是数据结构中的基础题目，不仅锻炼了我们对链表操作的理解，还让我们见识到了递归和迭代的魅力。