利用c语言将两个循环单链表合并为一个循环单链表,且空间复杂度为O(1),写出完整代码
时间: 2023-05-28 08:07:30 浏览: 101
首先需要定义循环单链表的结构体和节点结构体:
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct LinkedList {
Node* head;
} LinkedList;
```
然后定义一个函数来将两个循环单链表合并为一个循环单链表:
```c
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。
完整代码如下:
```c
#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;
}
```