合并单链表 数据结构与算法

Question

题目描述
创建两个有序单链表，然后，把这两个有序单链表合并成一个有序单链表。
输入
第一行：第一个单链表的元素个数
第二行：输入第一个有序单链表。
第三行：第二个单链表的元素个数
第四行：输入第二个有序单链表。

输出
第一行：输出合并之后的单链表。
样例输入 复制
5
1 2 4 5 6
4
3 7 8 9
样例输出 复制
1 2 3 4 5 6 7 8 9
请问各位知道这怎么做吗

Answer 1

引自免费微信小程序：皆我百晓生

为了合并两个有序的单链表，你可以采用迭代或递归的方法。这里我将提供一个使用迭代法的C++解决方案：

首先，定义链表节点结构体：

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

然后编写合并函数：

ListNode* mergeTwoSortedLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    ListNode dummy(-1); // 创建一个虚拟头节点
    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; // 返回合并后的新链表头节点
}

// 为了处理输入格式，可以创建以下辅助函数来读取链表（假设有getline和stoi函数可用）
vector<ListNode*> readLinkedLists() {
    vector<ListNode*> lists;
    int n1, n2;
    cin >> n1;
    for (int i = 0; i < n1; ++i) {
        int val;
        cin >> val;
        if (i == 0) {
            lists.push_back(new ListNode(val));
            ListNode* current = lists.back();
        } else {
            current->next = new ListNode(val);
            current = current->next;
        }
    }
    cin >> n2;
    for (int i = 0; i < n2; ++i) {
        int val;
        cin >> val;
        if (lists.empty() || !lists.back()->next) {
            lists.push_back(new ListNode(val));
            ListNode* current = lists.back();
        } else {
            current->next = new ListNode(val);
            current = current->next;
        }
    }
    return lists;
}

int main() {
    vector<ListNode*> linkedLists = readLinkedLists();
    ListNode* mergedListHead = mergeTwoSortedLists(linkedLists[0], linkedLists[1]);

    // 这里省略了输出合并后链表的代码，你可以自行实现打印链表的功能

    // 不要忘记释放链表内存
    // ...
    
    return 0;
}

这段代码首先定义了一个链表节点结构体ListNode，然后实现了合并两个有序链表的函数mergeTwoSortedLists。为了处理题目中的输入格式，我还给出了一个辅助函数readLinkedLists用于从输入流中读取并构造两个有序链表。

注意在实际环境中，你需要为链表元素分配内存，并在程序结束时正确地释放这些内存以防止内存泄漏。上述示例代码未包含这部分内容。