设单链表以非递增有序排列,设计一个算法删去单链表中值相同的多余节点。要求:算法的时间复杂度是 O(n),空间复杂度是O(1)。 输入描述: 输入表中初始数据元素的个数n,占一行; 输入n个整型数据元素(元素按值非递增有序排列),以空格隔开,占一行 c语言代码
时间: 2024-09-18 21:01:54 浏览: 5
为了删除单链表中值相同的多余节点并保持非递增有序,我们可以采用两个指针`current`和`previous`的方式来遍历链表。以下是C语言的基本步骤:
1. 定义一个结构体`ListNode`表示链表节点,包含`value`和`next`两个字段。
```c
typedef struct ListNode {
int value;
struct ListNode* next;
} ListNode;
```
2. 创建一个函数`deleteDuplicates`接收链表头作为参数,并设置两个指针。
```c
void deleteDuplicates(ListNode** head) {
if (*head == NULL || (*head)->next == NULL) {
return; // 如果链表为空或者只有一个元素,直接返回
}
ListNode *current = *head;
ListNode *previous = NULL;
```
3. 遍历链表,比较当前节点的值和前一个节点的值。
```c
while (current != NULL) {
if (current->value == previous->value) {
// 如果当前值等于前一个值,删除当前节点
ListNode* temp = current;
previous->next = current->next;
free(temp); // 释放当前节点的内存
} else {
// 如果不相等,将当前节点设置为下一个节点,并更新前一个节点
previous = current;
current = current->next;
}
}
}
```
4. 更新链表头指针,因为可能已经移除了第一个元素。
```c
*head = previous;
}
```
5. 提供函数入口。
```c
int main() {
// 实际调用 deleteDuplicates 函数,传递链表头指针
// 其他链表初始化代码...
deleteDuplicates(&head);
// ...
return 0;
}
```