已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。

将两个链表连接在一起，实际上就是将 L2 链接到 L1 的末尾。因为已经给出了链表的长度 m 和 n，因此可以先遍历 L1 到其末尾，然后将 L2 连接到 L1 的末尾即可。时间复杂度为 $O(m)$。

下面是算法的具体实现（C++ 代码）：

ListNode* joinTwoLists(ListNode* L1, ListNode* L2) {
    if (L1 == NULL) {
        return L2;
    }
    ListNode* p = L1;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = L2;
    return L1;
}

其中，ListNode 是链表节点的结构体，包含一个值 val 和一个指向下一个节点的指针 next。L1 和 L2 分别是两个链表的头节点指针。

相关问题

已知L1、L2分别为两循环单链表的头结点2指针，m，n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。

要合并两个循环单链表 L1 和 L2 成为一个新的循环链表，我们可以使用以下步骤设计算法：

1. **初始化新链表**:
创建一个新的循环链表，其头节点 `newHead` 设置为一个空节点，同时设置一个临时节点 `temp` 用于辅助连接操作。

2. **比较并链接节点**:
- 当 `L1` 或 `L2` 非空时：
- 比较当前 `L1->next` 和 `L2->next` 的值，选择较小的一个作为新的链表节点，将较大的那个指向 `temp`，然后移动较小的那个到 `temp->next`。
- 将当前节点的下一个指针指向下一个小的节点。
- 如果其中一个链表为空，将另一个链表的剩余部分接到新链表的末尾。

3. **处理尾部连接**:
- 当遍历完其中一个链表时，将另一个链表的剩余部分接到新链表的末尾。这可以通过让 `temp->next = newHead` 来完成，因为 `temp` 现在指向原链表的最后一个元素。
- 为了形成循环链表，我们需要更新 `temp->next = temp`，使得尾部再次回到开始。

4. **返回新链表头部**:
返回 `newHead` 作为合并后的链表的头节点。

这是一个线性的算法，时间复杂度为 O(m + n)，其中 m 和 n 分别是 L1 和 L2 的长度。下面是伪代码形式描述：

function mergeCircularLists(L1, L2):
    newHead = EmptyNode()
    temp = newHead

    while L1 is not None and L2 is not None:
        if L1.value < L2.value:
            temp.next = L1
            L1 = L1.next
        else:
            temp.next = L2
            L2 = L2.next
        temp = temp.next
    
    # If one list is finished, append the other to the end
    if L1 is None:
        temp.next = L2
        temp.next.next = newHead
    else:
        temp.next = L1
        L1.next = newHead

    return newHead

已知L1、L2分别为两循环单链表的头结点指针， m , n 分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。C语言

在C语言中，为了合并两个已排序的循环链表L1和L2，可以按照以下步骤设计算法：

1. **初始化新链表**：
创建一个新的循环链表，头部节点设为`head`，并将其`next`指向`NULL`。

2. **比较并插入元素**：
- 使用两个指针`p1`和`p2`分别指向L1和L2的当前节点。
- 初始化两个临时指针`temp1`和`temp2`，它们都指向`NULL`，用于临时存放较小值的节点。
- 当`p1`或`p2`不为空时：
a. 比较`p1->data`和`p2->data`的大小，选择较小的节点作为下一个节点添加到新链表中。
- 如果`p1->data < p2->data`，将`p1`移动一位，并将`temp1->next = p1`，然后更新`temp1 = p1`。
- 否则，如果`p2->data <= p1->data`，同样地，将`p2`移动一位，并将`temp2->next = p2`，然后更新`temp2 = p2`。
b. 然后将当前的`temp1`或`temp2`作为新链表的当前节点，即`head->next = temp1->next`（因为是循环链表，需要设置`head->next = head`），并将`head`前进一位。

3. **结束条件**：
- 当`p1`和`p2`均为空时，说明已经处理完了一个列表的所有元素。此时，将另一个列表剩余部分连接到新链表的末尾：`head->next = (p1 == NULL) ? L2 : L1`。

4. **返回合并后的链表**：
最终返回新链表的头节点`head`。

以下是简化版的伪代码示例：

typedef struct Node {
    int data;
    struct Node* next;
} ListNode;

ListNode* mergeCircularLists(ListNode* L1, ListNode* L2) {
    ListNode* head = new ListNode();
    ListNode* temp1 = temp2 = head;
    ListNode* p1 = L1, *p2 = L2;
    while (p1 && p2) {
        if (p1->data < p2->data) {
            temp1->next = p1;
            temp1 = p1++;
        } else {
            temp2->next = p2;
            temp2 = p2++;
        }
        temp1->next->next = temp2->next;
    }
    // 将剩余部分连接至链尾
    if (p1) {
        temp1->next = L2;
    } else {
        temp2->next = L1;
    }
    temp1->next->next = head; // 设置循环链接
    return head;
}