给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 head = [1,2,6,3,4,5,6], val = 6
时间: 2024-10-06 19:05:45 浏览: 19
要删除链表中所有值为 `val` 的节点,我们可以使用迭代或递归的方式遍历链表。这里我将提供一个使用迭代的方法:
首先,我们需要创建一个新的头节点 `new_head` 和两个指针 `prev` 和 `current`。`prev` 指针始终指向前一个节点,而 `current` 则用来遍历链表。
当遇到值等于 `val` 的节点时,我们将不将其添加到新的链表中,而是直接跳过它。如果当前节点不是要删除的,我们就将它的下一个节点赋给 `prev`,然后继续向前移动 `current`。当遍历完后,`prev` 就指向了新链表的最后一个节点(如果没有被删除的节点),所以我们把 `prev` 设置为新链表的头节点。
下面是相应的 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* removeElements(ListNode* head, int val) {
if (head == NULL || head->val != val) {
return head;
}
ListNode* new_head = NULL;
ListNode* prev = NULL;
ListNode* current = head;
while (current != NULL && current->val == val) {
current = current->next; // 直接跳过值为val的节点
}
if (current != NULL) { // 如果链表中有其他节点
prev = current;
current = current->next;
} else {
return NULL; // 如果链表只包含要删除的节点,则返回NULL
}
while (current != NULL) {
prev->next = current->next;
prev = prev->next;
if (prev->next == NULL) { // 遍历结束后,prev即为新链表的末尾
break;
}
if (prev->next->val == val) { // 内部循环检查并跳过剩余的val节点
prev->next = prev->next->next;
} else {
current = prev->next;
}
}
return new_head ? new_head : current; // 返回非空的新链表头节点
}
// 示例:
void printList(ListNode* node) {
while (node != NULL) {
printf("%d -> ", node->val);
node = node->next;
}
printf("NULL\n");
}
int main() {
ListNode* head = malloc(sizeof(ListNode));
head->val = 1;
head->next = malloc(sizeof(ListNode));
head->next->val = 2;
head->next->next = malloc(sizeof(ListNode));
head->next->next->val = 6;
head->next->next->next = malloc(sizeof(ListNode));
head->next->next->next->val = 3;
head->next->next->next->next = malloc(sizeof(ListNode));
head->next->next->next->next->val = 4;
head->next->next->next->next->next = malloc(sizeof(ListNode));
head->next->next->next->next->next->val = 5;
head->next->next->next->next->next->next = malloc(sizeof(ListNode));
head->next->next->next->next->next->next->val = 6;
head->next->next->next->next->next->next->next = NULL;
printf("Original list: ");
printList(head);
int valToRemove = 6;
ListNode* newHead = removeElements(head, valToRemove);
printf("New list after removing %d: ", valToRemove);
printList(newHead);
return 0;
}
```
运行这段代码后,你会看到原链表 `[1,2,6,3,4,5,6]` 删除所有 `6` 后的结果。如果你有其他关于这个操作的问题,或者需要帮助理解代码,请告诉我。
阅读全文