面试题：C++ 循环链表的合并与排序

链表节点定义：

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

合并函数：

ListNode* mergeTwoCircularLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    ListNode dummy(0);
    ListNode* tail = &dummy;
    ListNode* p1 = l1;
    ListNode* p2 = l2;
    do {
        if (p1->val <= p2->val) {
            tail->next = p1;
            p1 = p1->next;
        } else {
            tail->next = p2;
            p2 = p2->next;
        }
        tail = tail->next;
    } while (p1 != l1 && p2 != l2);
    while (p1 != l1) {
        tail->next = p1;
        p1 = p1->next;
        tail = tail->next;
    }
    while (p2 != l2) {
        tail->next = p2;
        p2 = p2->next;
        tail = tail->next;
    }
    tail->next = dummy.next;
    return dummy.next;
}

测试代码：

#include <iostream>
int main() {
    // 创建第一个循环链表: 1 -> 3 -> 5 -> 1
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);
    l1->next->next->next = l1;

    // 创建第二个循环链表: 2 -> 4 -> 6 -> 2
    ListNode* l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);
    l2->next->next->next = l2;

    ListNode* mergedList = mergeTwoCircularLists(l1, l2);

    // 输出合并后的循环链表
    ListNode* current = mergedList;
    do {
        std::cout << current->val << " ";
        current = current->next;
    } while (current != mergedList);
    std::cout << std::endl;

    return 0;
}

时间复杂度分析：
- 合并过程中，我们需要遍历两个链表的所有节点。假设第一个链表长度为 n，第二个链表长度为 m，则总共需要遍历 n + m 个节点。所以时间复杂度为 (O(n + m))。
空间复杂度分析：
- 除了输入的链表和输出的合并链表外，我们只使用了常数级别的额外空间，如 dummy 节点和几个指针变量。所以空间复杂度为 (O(1))。

星途面试题库

面试题：C++ 循环链表的合并与排序

知识考点

面试题答案