已知有一个带头结点的无序单链表,元素值为正整数且不重复,将链表中元素最小值结点删除,写出算法思想并给出c语言或c++代码实现。
时间: 2024-09-30 22:05:36 浏览: 41
顺序输入数据元素的值建立带头结点的单链表-数据结构第一章
算法思想:
1. 初始化两个指针,一个指向当前节点(current),另一个指向最小节点(min_node)。初始化时,假设头节点就是最小节点。
2. 遍历链表,比较当前节点的值与已知最小值,如果当前节点的值更小,则更新min_node指向当前节点。
3. 在遍历过程中,同时记录下一个最小节点候选者(next_min),以便在找到最小节点后可以跳过它(因为删除最小节点后,下一个节点可能是新的最小值)。
4. 当找到最小节点后,更新其前驱节点的next指针,使其指向最小节点的下一个节点,完成删除操作。
5. 最后返回原链表的头节点作为新的第一个节点。
以下是C语言的实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 找到链表中的最小节点
ListNode* findMin(ListNode* head) {
ListNode* min_node = head;
ListNode* current = head->next;
while (current != NULL) {
if (current->val < min_node->val) {
min_node = current;
}
current = current->next;
}
return min_node;
}
// 删除链表中的最小节点
ListNode* deleteMin(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head; // 如果链表只有一个元素或为空,直接返回
}
ListNode* min_node = findMin(head);
ListNode* prev_node = head;
if (min_node == head) { // 如果最小节点是头节点
prev_node->next = min_node->next;
} else {
prev_node->next = min_node->next;
}
free(min_node); // 释放最小节点的内存
return head;
}
// 打印链表
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
printf("%d ->", temp->val);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
// 创建并初始化链表
ListNode* list = (ListNode*)malloc(sizeof(ListNode));
list->val = 4;
list->next = (ListNode*)malloc(sizeof(ListNode));
list->next->val = 2;
list->next->next = (ListNode*)malloc(sizeof(ListNode));
list->next->next->val = 3;
list->next->next->next = (ListNode*)malloc(sizeof(ListNode));
list->next->next->next->val = 1;
list->next->next->next->next = NULL;
printf("Original List: \n");
printList(list);
list = deleteMin(list);
printf("List after deleting the minimum value: \n");
printList(list);
return 0;
}
```
上述代码首先创建了一个简单的链表,并在`main`函数中展示了如何找到并删除最小节点。记得处理完链表后,要手动释放不再使用的内存。
阅读全文