编写一c语言算法删除带头节点的单链表中值相同的多余结点,,即若链表中有多个结点具有相同的数据域,只保留其中一个结点,其余结点均从链表中删去,使得最后得到的链表中的所有结点的数据域都不相同
时间: 2024-10-06 20:05:20 浏览: 53
在C语言中,要编写一个算法来删除单链表中值相同且仅保留一个的多余节点,我们可以采用迭代或递归的方式。这里我将给出一种迭代的方法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 函数声明
Node* deleteDuplicates(Node* head);
// 遍历链表,遇到重复值则跳过非第一个出现的节点
Node* iterateDeleteDuplicates(Node* current, Node* previous) {
while (current != NULL) {
if (previous != NULL && previous->data == current->data) { // 如果当前节点值等于前一个节点值
Node* temp = current; // 保存当前节点
while (temp->next != NULL && temp->next->data == current->data) { // 跳过所有重复的节点
temp = temp->next;
}
current = temp->next; // 更新current指向下一个非重复节点
free(temp); // 释放重复节点的内存
} else {
previous = current; // 更新前一个节点指针
current = current->next;
}
}
return head; // 返回处理后的头节点
}
int main() {
// 初始化示例链表
Node* head = (Node*)malloc(sizeof(Node));
head->data = 1;
head->next = (Node*)malloc(sizeof(Node));
head->next->data = 2;
head->next->next = (Node*)malloc(sizeof(Node));
head->next->next->data = 3;
head->next->next->next = (Node*)malloc(sizeof(Node));
head->next->next->next->data = 2;
head->next->next->next->next = (Node*)malloc(sizeof(Node));
head->next->next->next->next->data = 4;
head = deleteDuplicates(head);
// 打印处理后的链表
Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
return 0;
}
// 删除链表中值相同节点的函数实现
Node* deleteDuplicates(Node* head) {
if (head == NULL || head->next == NULL) {
return head;
}
return iterateDeleteDuplicates(head, NULL);
}
```
这个程序首先检查链表是否为空或只有一个元素。然后,`iterateDeleteDuplicates`函数遍历链表,每当遇到重复值时,它会跳过所有后续的重复节点,并在适当的时候释放它们的内存。最后返回处理过的头节点。
阅读全文