郑州做商城网站公司,开发微信小程序流程,使用vue做的网站,网站通用样式文章目录 题目描述我的解法思路结果分析 官方题解分析 查漏补缺更新日期参考来源 题目描述
传送门 删除排序链表中的重复元素#xff1a;给定一个已排序的链表的头 head #xff0c; 删除所有重复的元素#xff0c;使每个元素只出现一次 。返回 已排序的链表 。 示例 1给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。 示例 1 输入head [1,1,2] 输出[1,2] 示例 2 输入head [1,1,2,3,3] 输出[1,2,3] 提示
链表中节点数目在范围 [0, 300] 内-100 Node.val 100题目数据保证链表已经按升序 排列
我的解法
/*** 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 nullptr;ListNode* slow head;ListNode* fast head-next;while(fast ! nullptr){// 快指针对应节点的值等于慢指针对应节点的值并且快指针不是表尾跳过重复元素if(fast-val slow-val fast-next ! nullptr){fast fast-next;}// 快指针对应节点的值等于慢指针对应节点的值但是快指针是表尾此时将慢指针指向nullptr然后结束循环else if(fast-val slow-val fast-next nullptr){slow-next nullptr;break;}// 快指针对应节点的值不等于慢指针对应节点的值else{slow-next fast;slow fast;fast fast-next;}}return head;}
};思路
由于链表本身是已排序的所以相等的元素一定相邻所以考虑使用快慢指针法通过快指针跳过重复的元素来解决问题。但是有一个关键点如果链表末尾存在重复元素则不能通过快指针跳过否则链表末尾重复的元素无法去掉这种情况需要单独考虑。
结果 分析
时间复杂度 循环遍历链表O(n)
空间复杂度 O(1)
官方题解
/*** 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* cur head;while (cur-next) {if (cur-val cur-next-val) {cur-next cur-next-next;}else {cur cur-next;}}return head;}
};分析
时间复杂度 O(n)其中n是链表的长度。
空间复杂度 O(1)
查漏补缺
对于链表的跳过某些元素通过一个节点便可以实现改变节点的指针并不需要双指针法。
更新日期
2024.1.14 欢迎前来讨论指正。
参考来源
力扣链接
