leetCode-83-Remove-Duplicates-from-Sorted-List
题目描述(简单难度)
给定一个链表,去重,每个数字只保留一个。
解法一 修改
按偷懒的方法,直接在 public ListNode deleteDuplicates(ListNode head) {
ListNode pre = new ListNode(0);
ListNode dummy = pre;
pre.next = head;
ListNode cur = head;
while(cur!=null && cur.next!=null){
boolean equal = false;
while(cur.next!=null && cur.val == cur.next.val){
cur = cur.next;
equal = true;
}
if(equal){
/*************修改的地方*****************/
//pre.next 指向 cur,不再跳过当前数字
pre.next = cur;
pre = cur;
/**************************************/
equal = false;
}else{
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur!=null && cur.next!=null){
//相等的话就删除下一个节点
if(cur.val == cur.next.val){
cur.next = cur.next.next;
//不相等就后移
}else{
cur = cur.next;
}
}
return head;
}
时间复杂度:O(n)。 空间复杂度:O(1)。 同样的,递归也会更简单些。 如果 阅读全文
递归
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
//如果头结点和后边的节点相等
if (head.next != null && head.val == head.next.val) {
//跳过所有重复数字
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
/*************修改的地方*****************/
//将 head 也包含,进入递归
return deleteDuplicates(head);
/**************************************/
//头结点和后边的节点不相等
} else {
//保留头结点,后边的所有节点进入递归
head.next = deleteDuplicates(head.next);
}
//返回头结点
return head;
}
解法二 迭代
解法三 递归
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){
return head;
}
//头结点和后一个时候相等
if(head.val == head.next.val){
//去掉头结点
return deleteDuplicates(head.next);
}else{
//加上头结点
head.next = deleteDuplicates(head.next);
return head;
}
}
总
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
![JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。](https://static.javajike.com/img/common/wx-fzp.png)
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com