设计一个算法,删除非空链表中所有值域为x的结点
时间: 2024-05-08 12:17:04 浏览: 21
算法思路:
1. 遍历链表,找到值域为x的结点。
2. 使用一个prev指针指向当前结点的前一个结点,然后删除当前结点。
3. 删除结点后,将prev指针指向当前结点的下一个结点。
4. 如果链表头结点的值域为x,需要特殊处理,将头结点指向下一个结点。
算法实现:
```
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
ListNode* curr = head;
while (curr != NULL) {
if (curr->val == val) {
prev->next = curr->next;
delete curr;
curr = prev->next;
} else {
prev = curr;
curr = curr->next;
}
}
head = dummy->next;
delete dummy;
return head;
}
```
算法分析:
该算法时间复杂度为O(n),空间复杂度为O(1)。