某单链表中的元素非递减有序,编写算法删除值重复的多余元素,使得元素递增有序。
时间: 2024-10-11 22:09:54 浏览: 29
数据结构与算法 c++实现 //删除顺序递增表中的重复元素 //对单链表实现就地逆置 //删除递增单链表中的重复元素
5星 · 资源好评率100%
要解决这个问题,你可以遍历链表,并维护两个指针,一个用于当前元素,另一个用于检查后续是否有重复的元素。如果找到重复的元素,则跳过它,直到遇到不同的元素为止。以下是使用C语言实现的一个简单算法:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* deleteDuplicates(Node* head) {
if (head == NULL || head->next == NULL)
return head; // 链表为空或只有一个元素,直接返回
// 使用快慢指针找到第一个重复元素
Node* slow = head;
Node* fast = head->next;
while (fast != NULL && fast->next != NULL) {
if (fast->data == slow->data) {
slow = slow->next; // 跳过重复元素
} else {
slow = slow->next;
fast = fast->next->next;
}
}
// 分割链表为无重复区段和剩余区段
if (fast->data == slow->data) {
Node* temp = slow->next;
free(slow);
slow = head;
while (slow->next != temp) {
slow = slow->next;
}
slow->next = NULL;
}
// 返回去除了重复元素的新头节点
return head;
}
// 示例
void printList(Node* node) {
while (node != NULL) {
printf("%d ->", node->data);
node = node->next;
}
printf("NULL\n");
}
int main() {
Node* list = createLinkedList({1, 1, 2, 3, 4, 4, 5}); // 假设这是一个非递减有序的链表
printf("Original List (Non-decreasing and with duplicates):\n");
printList(list);
list = deleteDuplicates(list);
printf("\nList after removing duplicates (Increasing order):\n");
printList(list);
return 0;
}
// 假设createLinkedList是一个辅助函数,创建一个包含给定整数的链表
```
在这个例子中,我们首先找到第一个重复元素,然后分割链表,删除重复区间的元素。最后,得到的就是一个递增有序且没有重复元素的新链表。
阅读全文