将两个循环单链表合并为一个循环单链表，且空间复杂度为O（1）

假设两个循环单链表分别为list1和list2，它们的头结点分别为head1和head2。

1. 如果list1和list2都为空，直接返回空链表。
2. 如果list1为空，返回list2。
3. 如果list2为空，返回list1。
4. 找到list1的尾结点tail1和list2的尾结点tail2。
5. 将tail1的next指向head2，将tail2的next指向head1。
6. 返回list1的头结点head1。

代码如下：

def merge_circular_linked_list(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1
    # 找到两个链表的尾结点
    tail1 = list1
    while tail1.next != list1:
        tail1 = tail1.next
    tail2 = list2
    while tail2.next != list2:
        tail2 = tail2.next
    # 合并两个链表
    tail1.next = list2
    tail2.next = list1
    return list1

相关问题

利用c语言将两个循环单链表合并为一个循环单链表，且空间复杂度为O（1），写出完整代码

首先需要定义循环单链表的结构体和节点结构体：

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

typedef struct LinkedList {
    Node* head;
} LinkedList;

然后定义一个函数来将两个循环单链表合并为一个循环单链表：

LinkedList* mergeLinkedList(LinkedList* list1, LinkedList* list2) {
    if (list1->head == NULL) {
        return list2;
    }
    if (list2->head == NULL) {
        return list1;
    }
    Node* list1Tail = list1->head;
    while (list1Tail->next != list1->head) {
        list1Tail = list1Tail->next;
    }
    Node* list2Tail = list2->head;
    while (list2Tail->next != list2->head) {
        list2Tail = list2Tail->next;
    }
    list1Tail->next = list2->head;
    list2Tail->next = list1->head;
    free(list2);
    return list1;
}

该函数首先判断两个链表是否为空，如果其中一个为空，则返回另一个链表。接着，找到两个链表的尾节点，分别为list1Tail和list2Tail。然后将list2的头节点插入list1的尾部，再将list1的头节点插入list2的尾部，即可完成合并。最后释放list2的内存空间，返回list1。

完整代码如下：

#include <stdio.h>
#include <stdlib.h>

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

typedef struct LinkedList {
    Node* head;
} LinkedList;

LinkedList* mergeLinkedList(LinkedList* list1, LinkedList* list2) {
    if (list1->head == NULL) {
        return list2;
    }
    if (list2->head == NULL) {
        return list1;
    }
    Node* list1Tail = list1->head;
    while (list1Tail->next != list1->head) {
        list1Tail = list1Tail->next;
    }
    Node* list2Tail = list2->head;
    while (list2Tail->next != list2->head) {
        list2Tail = list2Tail->next;
    }
    list1Tail->next = list2->head;
    list2Tail->next = list1->head;
    free(list2);
    return list1;
}

int main() {
    LinkedList* list1 = (LinkedList*)malloc(sizeof(LinkedList));
    LinkedList* list2 = (LinkedList*)malloc(sizeof(LinkedList));
    LinkedList* mergedList;

    Node* node1 = (Node*)malloc(sizeof(Node));
    node1->data = 1;
    Node* node2 = (Node*)malloc(sizeof(Node));
    node2->data = 2;
    Node* node3 = (Node*)malloc(sizeof(Node));
    node3->data = 3;

    node1->next = node2;
    node2->next = node3;
    node3->next = node1;
    list1->head = node1;

    Node* node4 = (Node*)malloc(sizeof(Node));
    node4->data = 4;
    Node* node5 = (Node*)malloc(sizeof(Node));
    node5->data = 5;
    Node* node6 = (Node*)malloc(sizeof(Node));
    node6->data = 6;

    node4->next = node5;
    node5->next = node6;
    node6->next = node4;
    list2->head = node4;

    mergedList = mergeLinkedList(list1, list2);

    Node* currentNode = mergedList->head;
    do {
        printf("%d ", currentNode->data);
        currentNode = currentNode->next;
    } while (currentNode != mergedList->head);
    printf("\n");

    free(node1);
    free(node2);
    free(node3);
    free(node4);
    free(node5);
    free(node6);
    free(list1);
    free(list2);
    free(mergedList);
    return 0;
}

利用c语言将两个循环单链表合并为一个循环单链表，且要求空间复杂度为O(1)，写出最简单的完整代码

#include <stdio.h>
#include <stdlib.h>

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

Node *merge(Node *head1, Node *head2) {
    if (head1 == NULL) return head2;
    if (head2 == NULL) return head1;

    Node *tail1 = head1->next;
    while (tail1->next != head1) tail1 = tail1->next;
    tail1->next = head2->next;
    free(head2);
    return head1;
}

int main() {
    Node *head1 = (Node*)malloc(sizeof(Node));
    head1->data = 1;
    head1->next = (Node*)malloc(sizeof(Node));
    head1->next->data = 3;
    head1->next->next = (Node*)malloc(sizeof(Node));
    head1->next->next->data = 5;
    head1->next->next->next = head1;

    Node *head2 = (Node*)malloc(sizeof(Node));
    head2->data = 2;
    head2->next = (Node*)malloc(sizeof(Node));
    head2->next->data = 4;
    head2->next->next = (Node*)malloc(sizeof(Node));
    head2->next->next->data = 6;
    head2->next->next->next = head2;

    Node *head = merge(head1, head2);
    Node *p = head;
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);
    printf("\n");

    return 0;
}