C语言算法-解答删除排序链表中的重复元素算法问题的C语言实现
题目
给定一个已排序的链表，删除链表中所有重复出现的元素，使得每个元素只出现一次。
引言
链表是一种常见的数据结构，用于存储一系列元素。在某些情况下，我们需要对链表进行操作，以满足特定的需求。删除排序链表中的重复元素是一个经典的链表操作问题，通常需要考虑如何在原地进行修改。
在下面的部分中，我们将讨论如何使用C语言来解决这个问题。
算法思路
解决这个问题的一种常见方法是使用迭代。以下是该算法的详细思路：
- 初始化一个指针
current，指向链表的头节点。 - 遍历链表，逐个检查相邻节点的值是否相等。
- 如果相邻节点的值相等，说明存在重复元素，将当前节点的
next指针指向下一个节点的next指针，从而跳过重复元素。 - 如果相邻节点的值不相等，继续遍历链表。
- 当遍历完整个链表后，返回头节点，此时链表中已删除重复元素。
代码实现
下面是C语言中删除排序链表中的重复元素的代码实现：
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
struct ListNode {
int val;
struct ListNode* next;
};
struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL) {
return head;
}
struct ListNode* current = head;
while (current->next != NULL) {
if (current->val == current->next->val) {
struct ListNode* temp = current->next;
current->next = current->next->next;
free(temp);
} else {
current = current->next;
}
}
return head;
}
// 辅助函数：创建链表节点
struct ListNode* createNode(int val) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 辅助函数：创建链表
struct ListNode* createLinkedList(int* values, int n) {
if (n == 0) {
return NULL;
}
struct ListNode* head = createNode(values[0]);
struct ListNode* current = head;
for (int i = 1; i < n; i++) {
current->next = createNode(values[i]);
current = current->next;
}
return head;
}
// 辅助函数：打印链表
void printLinkedList(struct ListNode* head) {
struct ListNode* current = head;
while (current != NULL) {
printf("%d ", current->val);
current = current->next;
}
printf("\n");
}
int main() {
int values[] = {1, 1, 2, 3, 3};
int n = sizeof(values) / sizeof(values[0]);
struct ListNode* head = createLinkedList(values, n);
printf("原链表：");
printLinkedList(head);
struct ListNode* newHead = deleteDuplicates(head);
printf("删除重复元素后的链表：");
printLinkedList(newHead);
return 0;
}算法分析
这个删除排序链表中的重复元素的算法的时间复杂度是O(n)，其中n是链表的长度，因为我们需要遍历整个链表。空间复杂度是O(1)，因为我们只使用了常量额外空间来保存指针。
示例和测试
让我们使用一个示例来测试我们的删除排序链表中的重复元素的程序。假设我们有一个排序链表1 -> 1 -> 2 -> 3 -> 3。运行上述代码，我们将得到以下输出：
原链表：1 1 2 3 3
删除重复元素后的链表：1 2 3 这表明链表中的重复元素已被成功删除。
总结
删除排序链表中的重复元素是一个常见的链表操作问题，通常需要考虑如何在原地进行修改。在本文中，我们使用C语言实现了一个删除排序链表中的重复元素的算法。通过详细讨论算法思路、代码实现、算法分析以及示例和测试，我们希望读者能够理解并运用这一概念来解决类似的问题。这个问题在链表操作中具有一定的实际应用价值，因此对于熟练掌握链表操作的程序员来说是一个有用的技能。
