☆打卡算法☆LeetCode 83、删除排序链表中的重复元素 算法解析
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“ 给定一个排序的链表,删除重复的元素,使每个元素出现一次,返回排序后的链表。”题目链接:来源:力扣(LeetCode)链接:83...
推荐阅读
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
一、题目
1、算法题目
“ 给定一个排序的链表,删除重复的元素,使每个元素出现一次,返回排序后的链表。”
题目链接:
来源:力扣(LeetCode)
链接:83. 删除排序链表中的重复元素 - 力扣(LeetCode) (leetcode-cn.com)
2、题目描述
给定一个已排序的链表的头 head
, 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
示例 1:
输入: head = [1,1,2]
输出: [1,2]
示例 2:
输入: head = [1,1,2,3,3]
输出: [1,2,3]
二、解题
1、思路分析
这道题跟82题 删除排序链表中的重复元素 II 很像,不仅是名字像,题型也像。
82题是删除所有重复元素,83题是删除重复元素,每个元素只出现一次,还是可以根据82题的解题思路来。
由于链表是排好序的,重复的元素在链表中出现的位置一定是连续的,对链表进行一次遍历,删除重复的元素吗,就可以得到我们想要的结果。
用指针cur指向头节点,如果cur和cur.next元素相同,那么我们就将cur.next从链表中删除,否则就说明链表中不存在其他重复的元素,直接返回这个链表即可。
2、代码实现
代码参考:
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
3、时间复杂度
时间复杂度 : O(n)
其中n是链表的长度。
空间复杂度: O(1)
三、总结
这道题的关键在于去重,并且重复的元素一定是重复的这个要点去解题。
那么就可以一直指针指向头部,判断下一个指针的下一个节点是否是重复元素,重复就删除,不重复就移动到下一位继续。
如此,循环到最后就得到了我们想要的链表了。
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)