合并有序链表

// 定义链表节点结构
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 合并两个有序链表的函数
ListNode* mergeTwoLists(ListNode* head1, ListNode* head2) {
    if (head1 == nullptr) {
        return head2;
    }
    if (head2 == nullptr) {
        return head1;
    }

    ListNode* head = head1->val <= head2->val? head1 : head2;
    ListNode* cur1 = head->next;
    ListNode* cur2 = head == head1? head2 : head1;
    ListNode* pre = head;

    while (cur1 != nullptr && cur2 != nullptr) {
        if (cur1->val <= cur2->val) {
            pre->next = cur1;
            cur1 = cur1->next;
        } else {
            pre->next = cur2;
            cur2 = cur2->next;
        }
        pre = pre->next;
    }

    pre->next = cur1!= nullptr? cur1 : cur2;
    return head;
}
 

1. 节点结构定义：
使用struct定义了链表节点ListNode，包含一个存储节点值的int类型变量val和一个指向下一个节点的指针next，并通过构造函数初始化节点值，同时将next指针初始化为nullptr。

2. 函数定义：
mergeTwoLists函数接收两个指向链表头节点的指针head1和head2作为参数。

• 边界情况处理：
首先检查head1和head2是否为空，如果head1为空，直接返回head2；如果head2为空，直接返回head1。

• 确定合并后链表的头节点：
通过比较head1和head2的节点值，选择较小值的节点作为合并后链表的头节点head。

• 初始化指针：
根据选择的头节点，初始化cur1为头节点的下一个节点，cur2为另一个链表的头节点，pre为头节点。

• 合并过程：
进入while循环，只要cur1和cur2都不为空，就比较cur1和cur2的节点值，将较小值的节点连接到pre的下一个节点，然后更新相应的指针。

• 处理剩余节点：
当循环结束后，说明其中一个链表已经遍历完，将另一个链表剩余的节点连接到合并后链表的末尾。

• 返回结果：
最后返回合并后链表的头节点head。

https://github.com/algorithmzuo