难度：简单
一、题目描述：
二、解题分析：
递归是一个很直接的方法，想想斐波那契数列
from typing import List
###### leetcode 代码主体 ######
class Solution:
def mergeTwoLists(self, l1, l2):
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val ListNode:
prenode = ListNode(0)
【题目描述】
LeetCode 的第 21 题要求合并两个已排序的链表。这道题目属于数据结构中的链表问题，难度被标记为简单。目标是将两个有序链表（升序排列）合并成一个新的有序链表，并返回这个新链表的头节点。
【解题思路】
解决这个问题有多种方法，但这里主要介绍一种常见的递归解决方案。我们可以将问题简化为一个递归的基本情况：如果其中一个链表为空，那么另一个链表就是结果；否则，比较两个链表头节点的值，将较小的那个值作为新链表的头节点，然后对剩下的部分继续进行相同的操作。
**递归方法**：
1. 检查 `l1` 和 `l2` 是否为空。如果 `l1` 为空，返回 `l2`；如果 `l2` 为空，返回 `l1`。
2. 比较 `l1` 和 `l2` 的头节点值。将较小值的节点作为新链表的头节点，记作 `new_head`。
3. 递归调用 `mergeTwoLists()` 函数，处理 `l1` 或 `l2` 的下一个节点（取决于当前哪个节点的值较小）。
4. 返回 `new_head`。
**非递归方法**：
1. 创建一个新的虚拟头节点 `prenode`，其 `next` 指针指向 `None`。
2. 使用一个临时指针 `lastnode` 指向 `prenode`。
3. 循环遍历两个链表 `l1` 和 `l2`，每次将较小值的节点添加到新链表中，并更新 `lastnode` 以指向新插入的节点。
4. 当遍历完两个链表后，返回 `prenode.next` 作为新的合并后的链表头。
在提供的代码中，作者使用了非递归方法来实现。首先定义了一个辅助函数 `generateList()` 将列表转换为链表，然后创建了 `Solution` 类，其中包含 `mergeTwoLists()` 方法。在 `mergeTwoLists()` 方法中，通过循环比较 `l1` 和 `l2` 的节点值，不断构建新的链表。将 `l1` 和 `l2` 转换为链表并调用 `mergeTwoLists()` 方法，输出合并后的链表。
**链表数据结构**：
链表是一种线性数据结构，其中的元素不连续存储，每个节点包含数据和指向下一个节点的引用。在这道题中，我们处理的是单链表，每个节点只有一个指向下一个节点的指针。
**代码实现**：
```python
from typing import List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
prenode = ListNode(0)
lastnode = prenode
while l1 is not None and l2 is not None:
if l1.val < l2.val:
lastnode.next = l1
l1 = l1.next
else:
lastnode.next = l2
l2 = l2.next
lastnode = lastnode.next
if l1 is not None:
lastnode.next = l1
elif l2 is not None:
lastnode.next = l2
return prenode.next
# 示例
l1 = [1, 2, 4]
l2 = [1, 3, 4]
solution = Solution()
merged_list = solution.mergeTwoLists(l1, l2)
```
在这个例子中，`l1` 和 `l2` 是表示链表的值列表，`Solution` 类的 `mergeTwoLists()` 方法将它们转换为链表并进行合并。最终，合并后的链表为 `[1, 1, 2, 3, 4, 4]`。
总结来说，LeetCode 第 21 题主要考察了链表操作和比较排序的知识。解题方法包括递归和迭代，这里主要展示了迭代方法，通过创建一个新链表并将两个输入链表的元素按顺序插入，实现有序链表的合并。这个过程需要对链表的基本操作（如创建、遍历和连接节点）有深入理解。
