c++合并两个有序链表 博客园

合并两个有序链表的基本思路是将两个链表按照大小顺序逐个比较，将较小的节点一个一个地插入到合并后的链表中。这个过程需要用到三个指针：一个指向合并后链表的头结点，另外两个分别指向两个原始链表的当前节点。

具体实现可以按照如下步骤：

1. 定义一个新链表的头和尾指针，初始时均指向NULL。
2. 从两个原始链表的头结点开始，比较两个节点的大小，将小的节点插入到新链表的尾部。
3. 将较小节点的指针向后移动一个单位，继续比较两个节点大小，直到其中一个链表的指针为空。
4. 将另一个链表剩余的节点直接插入到新链表的尾部。
5. 返回新链表的头指针，即为合并后的有序链表。

需要注意的是，在比较两个节点大小时，要使用它们存储的值进行比较，而非节点本身的地址。如果两个节点的值相等，则可以将任一个节点插入到新链表的尾部。

另外，为避免频繁地进行节点的插入操作，可以先比较两个节点的大小，将较小的节点存储到一个数组中，最后再将数组中的节点依次插入到新链表中。这样可以有效地提高算法的效率。

参考代码如下：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummy;
    struct ListNode *tail = &dummy;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    tail->next = l1 ? l1 : l2;

    return dummy.next;
}