删除链表中的重复结点
1、定义链表结构体Node.
2、实现单链表构建函数createLink,并使用createLink函数接收数据创建单链表,并返回链表头指针。
3、完成函数dubdel的编写,该函数删除单向链表中的重复结点,如果链表中存在重复结点(除next指针外的其它
数据成员的值相同)时,保留离链首最近的结点,然后返回链表头指针。
4、输出删除重复值后的单链表的值。
输入以-1结束
样例输入:12324-1
样例输出:1234
怎么写一个简单易懂程序
注意:使用这个结构
struct Node {
int data;
struct Node* next;
};
struct Node* createLink(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
struct Node* dubdel(struct Node* head) {
if (head == NULL || head->next == NULL) { // 如果链表为空或只有一个节点,则直接返回头节点
return head;
}
Node* p = head; // 定义一个指针p指向头节点
Node* pre = NULL; // 定义一个指针pre用于记录上一个节点的位置
Node* cur = p->next; // 定义一个指针cur用于遍历链表中的下一个节点
p->next = NULL; // 将头节点的next指针置为NULL,方便后续操作
while (cur != NULL) { // 当cur不为NULL时,继续遍历链表中的下一个节点
if (cur->data == p->data) { // 如果当前节点的数据域与前一个节点的数据域相同,说明出现了重复结点
if (pre == NULL) { // 如果pre为NULL,说明第一个重复结点在链表头部,需要将其删除并将p指向它后面的节点
p = p->next;
} else if (cur == pre->next) { // 如果当前节点是前一个节点的下一个节点,说明重复结点在链表中间,需要将其删除并将p指向它后面的节点
pre->next = cur->next;
p = p->next;
} else if (cur == p->next) { // 如果当前节点是p节点的下一个节点,说明重复结点在链表尾部,需要将其删除并将p指向它前面的节点
p->next = cur->next;
p = p->next;
} else { // 如果当前节点既不是第一个也不是最后一个重复结点,说明出现了多个重复结点,需要将其删除并将p指向它前面的节点
pre->next = cur->next;
p = p->next;
}
} else { // 如果当前节点的数据域与前一个节点的数据域不同,说明没有重复结点,直接将p指向下一个节点
pre = p;
p = p->next;
}
cur = p->next; // 将cur指向下一个节点,继续遍历链表中的下一个节点
}
return head; // 返回头节点
}
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* dubdel(struct Node* head) {
if (head == NULL) {
return NULL;
}
struct Node* current = head;
while (current != NULL) {
struct Node* runner = current;
while (runner->next != NULL) {
if (runner->next->data == current->data) {
struct Node* temp = runner->next;
runner->next = runner->next->next;
free(temp);
} else {
runner = runner->next;
}
}
current = current->next;
}
return head;
}
struct Node* createLink() {
struct Node* head = NULL;
struct Node* tail = NULL;
int data;
printf("请输入链表数据(以-1结束):\n");
while (scanf("%d", &data) == 1 && data != -1) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
return head;
}
void printList(struct Node* head) {
printf("删除重复值后的链表:");
struct Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
struct Node* head = createLink();
head = dubdel(head);
printList(head);
return 0;
}