【题目】
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入： l1 = [1,2,4], l2 = [1,3,4]
输出： [1,1,2,3,4,4]
示例 2：
输入： l1 = [], l2 = []
输出： []
示例 3：
输入： l1 = [], l2 = [0]
输出： [0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100-
l1和l2均按 非递减顺序 排列
【题目解析】
思路：
合并两个有序链表的问题可以通过直观且有效的双指针方法解决，该方法保证了时间复杂度为 O(n + m)，其中 n 和 m 是两个链表的长度。核心思想是创建两个指针，分别遍历两个链表，每次只移动一个节点到结果链表中，通过比较两个链表当前节点的值，决定哪个节点应该先被加入到结果链表中。这样可以在保持顺序的同时完成合并过程。
算法步骤如下：
- 创建一个哑节点作为新链表的起始节点，它可以简化边界条件的处理。
- 创建两个指针，分别指向两个链表的头部。
- 比较两个指针所指节点的值，将较小值的节点链接到结果链表中，并移动该指针到下一个节点。
- 当一个链表被完全遍历后，将另一个链表剩余部分直接链接到结果链表的末尾。
- 返回哑节点的下一个节点，即合并后链表的头部。
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:
# 创建一个哑节点，它将是合并后链表的起始节点
dummy = ListNode(-1)
prev = dummy
# 当两个链表都不为空时，比较它们的头节点的值
# 将较小的节点添加到合并后的链表中
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
# 如果有一个链表为空了，就将非空链表的剩余部分
# 直接连接到合并后的链表的最后一个节点上
prev.next = l1 if l1 is not None else l2
# 因为哑节点是合并后链表的起始节点的前一个节点
# 所以我们返回它的下一个节点作为合并后的链表的头节点
return dummy.next
执行：
【总结】
适用问题类型： 合并有序链表问题属于链表操作的范畴，特别是那些涉及有序数据结构的场景。这类方法适用于任何需要合并两个或多个已排序列表或链表的问题，无论它们是以升序还是降序排列。例如，合并多个日程安排、事件、已排序的数值等。该方法的优势在于保持了元素的有序性，同时合并了两个序列。
使用的算法： 解决合并有序链表问题的算法是迭代法，特别是双指针技术的应用。这种方法的关键在于同时迭代两个链表，每次只移动一个节点到新链表中，这个过程重复进行，直到所有节点都被遍历。实际上，这是一种归并操作，类似于归并排序中的合并过程。
算法细节：
- 初始化：创建一个哑结点（dummy node）作为新链表的头部，这样可以避免处理头结点为空的特殊情况。
- 迭代合并：创建两个指针，分别指向两个链表的当前节点。比较两个指针所指节点的值，将较小值的节点链接到新链表中，并移动对应的指针。
- 处理剩余节点：当一个链表先被遍历完，将另一个链表的剩余部分直接链接到新链表的末尾。
- 返回结果：新链表的头节点实际上是哑结点的下一个节点。
算法性能： 该算法的时间复杂度为 O(n + m)，其中 n 和 m 分别是两个链表的长度，因为它需要遍历每个链表一次。空间复杂度为 O(1)，因为合并操作在原有链表上进行，不需要额外的空间来存储新的链表。
总结： 合并两个有序链表的问题是链表操作中的一个基础而重要的问题，它不仅体现了双指针方法在实际应用中的高效性，而且突出了算法设计中的空间效率。这种技巧在处理排序、搜索以及分割和合并数据结构时非常有用。此外，该问题的解法也展示了如何在不增加额外空间负担的情况下，通过简单的迭代来优化和简化数据结构操作。掌握这种方法对于解决更复杂的数据处理问题是非常宝贵的。
