C语言完成链表节点的定义和初始化、查找、销毁等基本操作,再将(3,6,8,9)和(2,5,8,10,12,16)两个非递减的有序链表合并为一个非递增的有序链表,仍然用原来的存储空间,并且要有每步操作的注释。
时间: 2024-05-02 16:16:19 浏览: 11
链表节点的定义:
```c
struct ListNode {
int val;
struct ListNode *next;
};
```
链表节点的初始化:
```c
struct ListNode *initList() {
struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode)); // 创建头节点
if (head == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
head->next = NULL; // 头节点的 next 指针指向 NULL
return head;
}
```
链表节点的销毁:
```c
void destroyList(struct ListNode *head) {
if (head == NULL) {
return;
}
struct ListNode *temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp); // 释放节点的内存
}
}
```
链表节点的查找:
```c
struct ListNode *searchList(struct ListNode *head, int target) {
if (head == NULL) {
return NULL;
}
struct ListNode *p = head->next;
while (p != NULL && p->val != target) {
p = p->next;
}
return p;
}
```
链表节点的插入:
```c
void insertList(struct ListNode *head, int val) {
if (head == NULL) {
return;
}
struct ListNode *p = head;
while (p->next != NULL) {
p = p->next;
}
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode)); // 创建新节点
if (node == NULL) {
printf("Memory allocation failed!\n");
return;
}
node->val = val;
node->next = NULL;
p->next = node; // 将新节点插入到链表尾部
}
```
链表节点的删除:
```c
void deleteList(struct ListNode *head, int val) {
if (head == NULL) {
return;
}
struct ListNode *p = head;
while (p->next != NULL && p->next->val != val) {
p = p->next;
}
if (p->next == NULL) {
return;
}
struct ListNode *temp = p->next;
p->next = p->next->next; // 将节点从链表中删除
free(temp); // 释放节点的内存
}
```
合并两个非递减的有序链表为一个非递增的有序链表:
```c
struct ListNode* mergeLists(struct ListNode* l1, struct ListNode* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode)); // 创建头节点
if (head == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
head->next = NULL;
struct ListNode *p = head;
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode)); // 创建新节点
if (node == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
node->val = l1->val;
node->next = NULL;
p->next = node; // 将新节点插入到链表尾部
l1 = l1->next;
} else {
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode)); // 创建新节点
if (node == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
node->val = l2->val;
node->next = NULL;
p->next = node; // 将新节点插入到链表尾部
l2 = l2->next;
}
p = p->next;
}
if (l1 != NULL) {
p->next = l1;
}
if (l2 != NULL) {
p->next = l2;
}
struct ListNode *q = head->next;
if (q == NULL) {
return NULL;
}
struct ListNode *r = q->next;
if (r == NULL) {
return q;
}
struct ListNode *s = r->next;
q->next = NULL;
r->next = q;
while (s != NULL) {
q = r;
r = s;
s = s->next;
r->next = q;
}
head->next = r;
return head->next;
}
```
完整代码如下:
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)