(一)采用头插法创建单链表; (二)采用尾插法创建单链表; (三)单链表上插入结点算法; (四)在单链表中删除结点算法; (五)将单链表倒置(逆序存储); (六)将两个有序单链表合并为一个有序单链表。用C语言编写
时间: 2024-09-22 19:06:51 浏览: 18
(一)**头插法创建单链表:**
```c
struct Node {
int data;
struct Node* next;
};
void insertAtHead(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
```
(二)**尾插法创建单链表:**
```c
void insertAtTail(struct Node** head, int value) {
if (*head == NULL) {
*head = (struct Node*)malloc(sizeof(struct Node));
(*head)->data = value;
(*head)->next = NULL;
} else {
struct Node* current = *head;
while (current->next != NULL)
current = current->next;
current->next = (struct Node*)malloc(sizeof(struct Node));
current->next->data = value;
current->next->next = NULL;
}
}
```
(三)**单链表插入节点算法:**
```c
void insertNode(struct Node** head, int position, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (position == 0) { // 插入到头部
newNode->next = *head;
*head = newNode;
} else {
struct Node* current = *head;
for (int i = 0; i < position - 1 && current != NULL; i++)
current = current->next;
if (current != NULL) {
newNode->next = current->next;
current->next = newNode;
}
}
}
```
(四)**删除单链表节点:**
```c
void deleteNode(struct Node** head, int key) {
if (*head == NULL)
return;
struct Node* temp = *head, *prev = NULL;
if (temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL)
return;
prev->next = temp->next;
free(temp);
}
```
(五)**单链表反转(逆序存储):**
```c
void reverseList(struct Node** head) {
struct Node* prev = NULL;
struct Node* current = *head;
struct Node* nextTemp;
while (current != NULL) {
nextTemp = current->next;
current->next = prev;
prev = current;
current = nextTemp;
}
*head = prev;
}
```
(六)**合并两个有序单链表:**
```c
void mergeSortedLists(struct Node** first, struct Node** second) {
struct Node* result = NULL, *tail = NULL;
if (*first == NULL) {
*result = *second;
} else if (*second == NULL) {
*result = *first;
} else if ((*first)->data <= (*second)->data) {
result = *first;
tail = first;
*first = (*first)->next;
} else {
result = *second;
tail = second;
*second = (*second)->next;
}
while (*first != NULL || *second != NULL) {
if (*first == NULL) {
tail->next = *second;
break;
} else if (*second == NULL) {
tail->next = *first;
break;
} else if ((*first)->data <= (*second)->data) {
tail->next = *first;
tail = *first;
*first = (*first)->next;
} else {
tail->next = *second;
tail = *second;
*second = (*second)->next;
}
}
*result = result ? result : *second;
}
```