先将键盘输入的一组整数依次存入单链表,然后删除其中的最大最小元素,最后将其余元素逆序输出。用C语言单链表
时间: 2024-12-02 16:16:12 浏览: 44
这个题目可以分为三个步骤:
1. **创建单链表并插入整数**:
首先,你需要定义一个结构体`ListNode`表示链表节点,包含一个整数值`val`和指向下一个节点的指针`next`。然后,你可以创建一个函数如`insertToLinkedList`,接收一个整数数组和数组长度作为参数,遍历数组,每次将一个整数插入到链表的末尾。
```c
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
void insertToLinkedList(int arr[], int n, ListNode** head) {
ListNode* current = *head;
for (int i = 0; i < n; i++) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = arr[i];
newNode->next = NULL;
if (!current) {
*head = newNode;
} else {
while (current->next) {
current = current->next;
}
current->next = newNode;
}
}
}
```
2. **找到最大值和最小值,并删除它们**:
使用两个指针分别追踪当前最大值和最小值,同时遍历链表。当找到新的最大或最小值时,更新对应的指针。然后,利用头插法删除这两个节点。
```c
void deleteMinMax(ListNode** head) {
ListNode* minNode = *head;
ListNode* maxNode = *head;
ListNode* curr = *head;
while (curr && curr->next) {
if (curr->val > maxNode->val) {
maxNode = curr;
} else if (curr->val < minNode->val) {
minNode = curr;
}
curr = curr->next;
}
// 删除最小值节点
if (*head == minNode) {
*head = minNode->next;
} else {
ListNode* prev = *head;
while (prev->next != minNode) {
prev = prev->next;
}
prev->next = minNode->next;
}
// 删除最大值节点类似
if (maxNode != *head) {
ListNode* temp = *head;
while (temp->next != maxNode) {
temp = temp->next;
}
temp->next = maxNode->next;
}
}
```
3. **逆序剩余元素**:
通过双指针法,一个指针从头开始,另一个指针从尾开始,交换他们的节点值,直到两个指针相遇。注意处理特殊情况,如果链表只有一个元素或者为空。
```c
void reverseRemaining(ListNode** head) {
ListNode* prev = NULL;
ListNode* curr = *head;
ListNode* nextTemp = NULL;
while (curr != NULL) {
nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
*head = prev;
}
// 主函数示例
void mainProcedure(int arr[], int n) {
ListNode* head = NULL;
insertToLinkedList(arr, n, &head);
deleteMinMax(&head);
reverseRemaining(&head);
// 输出链表
displayLinkedList(head); // 这里需要自定义一个递归或迭代的函数来打印链表
}
```
阅读全文