难度: Easy
给定两个以 有序链表 形式记录的训练计划 l1、l2，分别记录了两套核心肌群训练项目编号，请合并这两个训练计划，按训练项目编号 升序 记录于链表并返回。
注意：新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
0 <= 链表长度 <= 1000
注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/
运行时间: 68 ms
内存: 15.2 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val > l2.val:
cur.next = l2
l2 = l2.next
else:
cur.next = l1
l1 = l1.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
此题解采用了双指针的方法来合并两个有序链表。通过设置一个虚拟头节点（dummy），利用一个指针（cur）迭代地选择两个链表中较小的节点加入到新链表中。当一个链表的节点被全部选完后，直接将另一个链表的剩余部分连接到新链表的末尾。这样，新链表最终将包含两个原链表的所有节点，且节点顺序为升序。
时间复杂度: O(n + m)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0) # 创建一个虚拟头节点
cur = dummy # 初始化当前节点为虚拟头节点
while l1 and l2: # 当两个链表均非空时进行循环
if l1.val > l2.val: # 比较两个链表头部的值
cur.next = l2 # 将较小值的节点接到新链表
l2 = l2.next # 移动较小值链表的指针
else:
cur.next = l1
l1 = l1.next
cur = cur.next # 移动新链表的指针
cur.next = l1 if l1 else l2 # 将未结束的链表接到新链表的末尾
return dummy.next # 返回虚拟头节点的下一个节点，即新链表的头节点
选择较小的节点是为了保持新链表的有序性。因为两个原链表都是有序的，通过每次选择两个链表中较小的节点并将其加入到新链表中，可以确保新链表也是按非降序排序。如果选择较大的节点，那么新链表将不再保持原有的顺序，可能需要额外的排序步骤。
如果两个链表的头节点值相等，选择哪个链表的节点加入新链表实际上并不影响最终结果的有序性。因此，可以任选其中一个。通常为了简化代码和逻辑，不需要特别指定哪个链表的节点先加入，只需保证有序性即可。
虚拟头节点（dummy head）主要用于简化链表操作，尤其是在链表头部可能发生变化的情况下。它提供了一个稳定的起始点，避免在合并过程中需要特别处理空链表的情况，同时也使得链表的头节点处理变得统一，便于管理和返回最终合并后的链表。
不会影响有序性。因为两个原链表已经是有序的，且在合并过程中保证了每次都是较小的节点先加入新链表。当其中一个链表的所有节点都已被加入新链表后，另一个链表的剩余部分仍然保持原有的顺序，因此直接将其接到新链表的末尾会继续保持整体的有序性。