给定两个按升序排列的单链表，需将其合并为一个保持升序的链表。该问题常见于数据结构与算法笔试题中，是链表操作的经典应用。

输入说明

• 第一行：第一个链表的节点数量 S1。
• 第二行：S1 个整数，表示第一个链表元素。
• 第三行：第二个链表的节点数量 S2。
• 第四行：S2 个整数，表示第二个链表元素。

输出要求

输出合并后的有序链表，各元素以空格分隔。

示例

输入：
4
2 4 6 8
3
3 5 7

输出：
2 3 4 5 6 7 8

核心思路

采用双指针法，分别遍历两个链表，比较当前节点值，将较小者加入结果链表，并移动对应指针。当其中一个链表遍历结束时，将另一个链表剩余部分直接接上。

代码实现（纯链表结构）

#include <bits/stdc++.h>
using namespace std;

// 定义链表节点结构体，包含数据域和指向下一节点的指针
struct ListNode {
    int val;
    ListNode* next;
    // 构造函数：初始化节点值并设置下一指针为空
    ListNode(int x) : val(x), next(nullptr) {}
};

// 向链表尾部插入新节点
void append(ListNode* head, int value) {
    ListNode* newNode = new ListNode(value);
    ListNode* curr = head;
    while (curr->next != nullptr) {
        curr = curr->next;
    }
    curr->next = newNode;
}

// 打印链表内容
void display(ListNode* head) {
    ListNode* curr = head->next;
    while (curr != nullptr) {
        cout << curr->val << ' ';
        curr = curr->next;
    }
}

int main() {
    // 创建两个虚拟头节点，便于统一处理插入逻辑
    ListNode* list1 = new ListNode(-1);
    ListNode* list2 = new ListNode(-1);

    int size1, size2, value;

    // 输入第一个链表
    cin >> size1;
    for (int i = 0; i < size1; ++i) {
        cin >> value;
        append(list1, value);
    }

    // 输入第二个链表
    cin >> size2;
    for (int i = 0; i < size2; ++i) {
        cin >> value;
        append(list2, value);
    }

    // 创建结果链表的虚拟头节点
    ListNode* result = new ListNode(-1);
    ListNode* tail = result;  // 指向当前尾部，用于追加节点

    ListNode* p = list1->next;  // 第一个链表的起始节点
    ListNode* q = list2->next;  // 第二个链表的起始节点

    // 双指针归并过程
    while (p != nullptr && q != nullptr) {
        if (p->val < q->val) {
            tail->next = p;
            p = p->next;
        } else {
            tail->next = q;
            q = q->next;
        }
        tail = tail->next;
    }

    // 接上剩余未处理的部分
    if (p != nullptr) {
        tail->next = p;
    }
    if (q != nullptr) {
        tail->next = q;
    }

    // 输出合并后的链表
    display(result);

    return 0;
}

该方法时间复杂度为 O(S1 + S2)，空间复杂度为 O(1)（不计输出），适用于链表结构的高效合并。