已知带头结点的单链表L,请写一算法,删除所有数据元素值为x的结点。要求:定义单链表的存储结构并分析算法的时间复杂度。
时间: 2024-10-18 12:18:50 浏览: 44
首先,我们需要定义链表的存储结构。假设链表中的每个节点有以下结构:
```c
typedef struct ListNode {
int data; // 节点数据
struct ListNode* next; // 指向下一個節點的指針
} ListNode;
```
对于删除所有数据元素值为x的结点的操作,我们可以采用迭代的方式,遍历整个链表,当遇到值为x的节点时,将其从链表中移除。以下是算法描述:
1. 定义三个指针:current(当前节点),previous(前一个节点),temp(临时节点)
2. 当current不是NULL并且data等于x时:
a. 将previous的next指向current的下一个节点
b. free(current);释放当前节点内存
c. current = previous的next;移动current到下一个节点
3. 否则,current和previous都向前移动一位,直到遍历完整个链表
时间复杂度分析:
- 这个算法的时间复杂度是O(n),其中n是链表的长度。因为无论链表有多长,我们最多需要访问每个节点一次。
```c
void deleteNodes(ListNode* head, int x) {
ListNode *current = head, *previous = NULL;
while (current != NULL && current->data == x) {
previous->next = current->next;
free(current);
current = previous->next;
}
}
```
阅读全文