题目描述
给定一个排序链表的头节点 head，删除链表中所有存在重复数字的节点，只保留原始排序链表中没有重复出现的元素。
示例 1：
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2：
输入: 1->1->1->2->3
输出: 2->3
解题思路
1. 排序链表的特性
由于链表已经是排序的，我们可以逐个遍历节点，检查当前节点是否是重复的。如果当前节点的值与下一个节点的值相同，就跳过这些重复的节点，直到遇到一个不同的节点。
2. 保留不重复的节点
为了删除所有重复元素，我们需要使用一个 dummy 节点，简化边界条件（例如删除头节点的情况）。我们需要一个指针 prev 来指向当前的非重复节点，遍历时检查当前节点是否与下一个节点重复：
- 如果当前节点的值与下一个节点相同，则跳过所有与当前节点值相同的节点。
- 如果当前节点的值与下一个节点不同，则保留当前节点，并将
prev指向当前节点。
3. 时间复杂度
遍历链表一次，时间复杂度是 O ( n ) O(n) O(n)，其中 n n n 是链表的节点数。
C语言实现
以下是 C 语言的实现代码：
#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
struct ListNode {int val;struct ListNode *next;
};// 删除排序链表中的重复元素 II
struct ListNode* deleteDuplicates(struct ListNode* head) {// 创建一个虚拟头节点struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));dummy->next = head;struct ListNode* prev = dummy; // prev 是指向当前不重复元素的前一个节点while (head != NULL) {// 如果当前节点的值与下一个节点的值相同if (head->next != NULL && head->val == head->next->val) {// 跳过所有重复节点while (head->next != NULL && head->val == head->next->val) {head = head->next;}// 删除重复元素prev->next = head->next;} else {// 当前节点不是重复节点，继续遍历prev = prev->next;}head = head->next;}struct ListNode* result = dummy->next;free(dummy); // 释放虚拟头节点return result;
}// 辅助函数：打印链表
void printList(struct ListNode* head) {while (head != NULL) {printf("%d", head->val);if (head->next != NULL) printf("->");head = head->next;}printf("\n");
}// 辅助函数：创建链表
struct ListNode* createList(int* arr, int size) {if (size == 0) return NULL;struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));head->val = arr[0];head->next = NULL;struct ListNode* temp = head;for (int i = 1; i < size; i++) {struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));node->val = arr[i];node->next = NULL;temp->next = node;temp = node;}return head;
}int main() {int arr1[] = {1, 2, 3, 3, 4, 4, 5};struct ListNode* head1 = createList(arr1, sizeof(arr1) / sizeof(arr1[0]));printf("Original list: ");printList(head1);head1 = deleteDuplicates(head1);printf("Modified list: ");printList(head1);int arr2[] = {1, 1, 1, 2, 3};struct ListNode* head2 = createList(arr2, sizeof(arr2) / sizeof(arr2[0]));printf("Original list: ");printList(head2);head2 = deleteDuplicates(head2);printf("Modified list: ");printList(head2);return 0;
}
代码详解
1. 链表结构
链表的节点由 struct ListNode 结构体表示，其中 val 存储节点值，next 是指向下一个节点的指针。
2. deleteDuplicates 函数
- 虚拟头节点：我们使用
dummy节点简化处理头节点的删除。 - 遍历链表：使用
prev记录当前非重复节点的前一个节点，head遍历每个节点。 - 删除重复节点：如果当前节点值与下一个节点相同，我们跳过所有重复的节点，将
prev->next指向第一个不同的节点。
3. createList 函数
根据数组创建链表，返回链表的头节点。
4. printList 函数
遍历链表并打印每个节点的值。
测试用例
示例 1
输入：
int arr1[] = {1, 2, 3, 3, 4, 4, 5};
输出：
Original list: 1->2->3->3->4->4->5
Modified list: 1->2->5
示例 2
输入：
int arr2[] = {1, 1, 1, 2, 3};
输出：
Original list: 1->1->1->2->3
Modified list: 2->3
