网站开发设计知乎,店铺名称设计logo设计,玩家世界网站建设,wordpress文章一部分加密原题链接
难度#xff1a;easy\color{Green}{easy}easy
题目描述
给定一个已排序的链表的头 headheadhead #xff0c; 删除所有重复的元素#xff0c;使每个元素只出现一次 。返回 已排序的链表 。
示例 1#xff1a; 输入#xff1a;head [1,1,2]
输出#xff1a;…原题链接
难度easy\color{Green}{easy}easy
题目描述
给定一个已排序的链表的头 headheadhead 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。
示例 1 输入head [1,1,2]
输出[1,2]
复制示例输入示例 2 输入head [1,1,2,3,3]
输出[1,2,3]
复制示例输入提示
链表中节点数目在范围 [0,300][0, 300][0,300] 内−100Node.val100-100 Node.val 100−100Node.val100题目数据保证链表已经按升序 排列 算法
(线性扫描) O(n)O(n)O(n)
从前往后扫描整个链表如果一个节点和其后继节点相同则直接删除后继节点否则指针移动到后继节点。
时间复杂度
整个链表只扫描一遍所以时间复杂度是 O(n)O(n)O(n)
C 代码
/*** 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) return head;ListNode* p head;while (p-next) {if (p-val p-next-val) p-next p-next-next;else p p-next;}return head;}
};
