合并两个有序链表

题目：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

思路：

1. 虚拟头结点：

   • 使用一个虚拟头结点（dummy）来简化链表操作。虚拟头结点的 next 指针指向合并后的链表的头结点。

   • 通过一个指针 p 来追踪新链表的最后一个节点。

2. 遍历链表：

   • 使用两个指针 p1 和 p2 分别遍历链表 l1 和 l2。

   • 比较 p1 和 p2 当前节点的值，将较小的节点连接到新链表的末尾。

   • 移动 p1 或 p2 指针到下一个节点。

3. 处理剩余节点：

   • 当其中一个链表遍历完毕后，将另一个链表的剩余部分直接连接到新链表的末尾。

4. 返回结果：

   • 返回虚拟头结点的 next 指针，即合并后的链表的头结点

代码：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) 
{// 虚拟头结点struct ListNode dummy;dummy.next = NULL;struct ListNode *p = &dummy;struct ListNode *p1 = l1, *p2 = l2;while (p1 != NULL && p2 != NULL) {// 比较 p1 和 p2 两个指针// 将值较小的节点接到 p 指针if (p1->val > p2->val) {p->next = p2;p2 = p2->next;} else {p->next = p1;p1 = p1->next;}// p 指针不断前进p = p->next;}// 将剩余部分接到 p 指针if (p1 != NULL) {p->next = p1;}if (p2 != NULL) {p->next = p2;}return dummy.next;
}