【问题描述】 给定一个链表,升序排列,要求删除其中的重复元素 【输入形式】 一个链表 【输出形式】 去重后的链表 【样例输入】 1 2 3 3 3 4 5 【样例输出】 1 2 3 4 5 【样例说明】 【评分标准】C语言
时间: 2024-10-11 22:02:46 浏览: 22
链表_链表_用链表将两个数组升序合并到另一个数组_
【问题描述】
给定一个已排序的链表,你需要编写一个程序来删除其中的重复元素,使得每个元素只保留第一次出现的值。输出应该是去重后的链表。链表节点通常包含整数值和指向下一个节点的指针。
【输入形式】
一个由整数构成的单向链表,比如:头结点的next字段指向下一个节点,最后一个节点的next为NULL。例如:
```c
struct ListNode {
int val;
struct ListNode *next;
};
ListNode* head = ...; // 链表的起始位置,初始值可能是 1 -> 2 -> 3 -> 3 -> 3 -> 4 -> 5 ...
```
【输出形式】
一个新链表,其中的元素按照原顺序且无重复,例如:
```c
ListNode* res_head = ...; // 新链表的起始位置,结果可能是 res_head -> 1 -> 2 -> 3 -> 4 -> 5 ...
```
【样例输入】
输入链表:1 -> 2 -> 3 -> 3 -> 3 -> 4 -> 5
【样例输出】
输出链表:1 -> 2 -> 3 -> 4 -> 5
【评分标准】
这个任务需要考虑如何遍历链表、存储已访问过的元素,并在遍历过程中删除重复项。时间复杂度的理想解决方案应该接近O(n),空间复杂度应尽可能低,最好为O(1)。提交的代码需要通过测试各种类型的链表,包括有大量重复元素的情况。
阅读全文