1.题目
题目地址(83. 删除排序链表中的重复元素 - 力扣（LeetCode）)
https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
题目描述
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2] 输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3] 输出：[1,2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
2.题解
2.1 一次遍历
思路
这里遍历链表，遇到重复的就删除重复的后一个节点，且当前节点cur不移动（防止接着的一个节点又等于cur->val）
否则我们向后移动cur，继续遍历。
代码
- 语言支持：C++
C++ Code:
* Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(head == nullptr) return head;ListNode *cur = head, *nt = head->next;while(cur->next != nullptr){if(cur->val == cur->next->val){ListNode *temp = cur->next;cur->next = temp->next;delete temp;}else{cur = cur->next;} }return head;}
};复杂度分析
令 n 为数组长度。
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
