cpp 合并两个有序链表

可以通过递归或迭代的方式实现合并两个有序链表。以下是迭代实现的示例代码：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    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;
}

int main() {
    ListNode a(1);
    ListNode b(2);
    ListNode c(4);
    a.next = &b;
    b.next = &c;

    ListNode d(1);
    ListNode e(3);
    ListNode f(4);
    d.next = &e;
    e.next = &f;

    ListNode* merged = mergeTwoLists(&a, &d);
    while (merged) {
        cout << merged->val << " ";
        merged = merged->next;
    }
    cout << endl;

    return 0;
}

在上面的代码中，我们创建了一个 dummy 节点作为合并后链表的头节点，使用 tail 指针指向当前已经合并的节点的末尾。然后，我们不断比较 l1 和 l2 的当前节点的值，将较小值的节点接到 tail 后面，同时将该链表的指针向后移动一位。最后，将剩余的链表接到 tail 后面即可。