用c语言设计在单链表中删除值相同的多余结点的算法。
时间: 2024-12-14 12:27:01 浏览: 15
在C语言中,设计一个删除单链表中重复值的算法可以分为两步:首先找到重复的值,然后删除多余的节点。这里我们可以创建一个新的节点并只保留第一次遇到的值,后续遇到相同值就替换掉当前节点。以下是一个简单的实现思路:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// 删除重复值节点的函数
void removeDuplicates(Node** head) {
if (*head == NULL) {
return;
}
Node* current = *head;
Node* prev = NULL;
while (current != NULL && current->next != NULL) {
if (current->data == current->next->data) { // 找到重复值
// 如果是第一个重复值,直接跳过
if (prev == NULL || prev->data != current->data) {
prev = current;
} else {
// 否则替换当前节点
Node* temp = current->next;
prev->next = current->next->next;
free(temp);
}
} else {
prev = current;
}
current = current->next;
}
}
// 打印链表
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
// 创建一个有重复值的链表,这里手动构建,实际应用中需要创建并填充
Node* list = createNode(1);
list->next = createNode(2);
list->next->next = createNode(3);
list->next->next->next = createNode(2);
list->next->next->next->next = createNode(1);
removeDuplicates(&list);
printList(list);
return 0;
}
```
这个算法会在遍历过程中删除重复的值,保留链表中首次出现的节点。注意,输入链表头的指针 `head` 传递给 `removeDuplicates` 函数,因为我们需要修改原链表。
阅读全文