视频字幕
我们要解决合并两个递增链表的问题。给定两个已经按递增顺序排列的链表，需要将它们合并成一个新的递增链表。例如，链表1包含1、3、5，链表2包含2、4、6，合并后应该得到1、2、3、4、5、6的递增序列。算法要求时间复杂度为O(n)，空间复杂度为O(1)。
解决这个问题的核心思路是使用双指针法。我们创建一个虚拟头节点作为结果链表的起点，然后使用两个指针分别指向两个输入链表的当前节点。通过比较两个指针指向节点的值，将较小的节点连接到结果链表中，并移动对应的指针。这个过程重复进行，直到其中一个链表遍历完毕，最后将剩余的节点直接连接到结果链表的末尾。
今天我们来解决一个经典的链表问题：合并两个递增链表。给定两个已经递增排序的链表，我们需要将它们合并成一个新的递增链表。例如，链表1包含1、2、4，链表2包含1、3、4，合并后的结果应该是1、1、2、3、4、4。这个问题要求时间复杂度为O(n)，空间复杂度为O(1)。
解决这个问题的关键是使用双指针技术。我们首先创建一个虚拟头节点，用来简化链表操作。然后使用两个指针分别指向两个链表的头节点。在每一步中，我们比较两个指针所指向节点的值，选择较小的那个节点连接到结果链表中，然后移动对应的指针。这个过程持续到其中一个链表完全遍历完毕，最后我们将剩余的非空链表直接连接到结果链表的末尾。
现在我们来看具体的算法实现。首先创建一个虚拟头节点，并用current指针指向它。然后进入主循环，当两个链表都不为空时，比较当前节点的值，将较小的节点连接到结果链表，并移动对应的指针。循环结束后，将剩余的非空链表直接连接到结果链表末尾。这个算法的时间复杂度是O(m+n)，其中m和n分别是两个链表的长度，空间复杂度是O(1)，只使用了常数个额外变量。
现在我们通过一个具体例子来演示算法的执行过程。假设链表1包含1、2、4，链表2包含1、3、4。首先创建虚拟头节点，用current指针指向它，p1和p2分别指向两个链表的头节点。第一步比较1和1，由于相等我们选择链表1的节点，将其连接到结果链表，然后移动p1指针。接下来比较2和1，选择较小的1，连接链表2的节点并移动p2。继续这个过程直到所有节点都被正确合并，最终得到1、1、2、3、4、4的递增序列。